MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  dchrhash Structured version   Visualization version   GIF version

Theorem dchrhash 25166
Description: There are exactly ϕ(𝑁) Dirichlet characters modulo 𝑁. Part of Theorem 6.5.1 of [Shapiro] p. 230. (Contributed by Mario Carneiro, 28-Apr-2016.)
Hypotheses
Ref Expression
sumdchr.g 𝐺 = (DChr‘𝑁)
sumdchr.d 𝐷 = (Base‘𝐺)
Assertion
Ref Expression
dchrhash (𝑁 ∈ ℕ → (♯‘𝐷) = (ϕ‘𝑁))

Proof of Theorem dchrhash
Dummy variables 𝑥 𝑎 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 eqid 2748 . . . . . 6 (ℤ/nℤ‘𝑁) = (ℤ/nℤ‘𝑁)
2 eqid 2748 . . . . . 6 (Base‘(ℤ/nℤ‘𝑁)) = (Base‘(ℤ/nℤ‘𝑁))
31, 2znfi 20081 . . . . 5 (𝑁 ∈ ℕ → (Base‘(ℤ/nℤ‘𝑁)) ∈ Fin)
4 sumdchr.g . . . . . 6 𝐺 = (DChr‘𝑁)
5 sumdchr.d . . . . . 6 𝐷 = (Base‘𝐺)
64, 5dchrfi 25150 . . . . 5 (𝑁 ∈ ℕ → 𝐷 ∈ Fin)
7 simprr 813 . . . . . . 7 ((𝑁 ∈ ℕ ∧ (𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ 𝑥𝐷)) → 𝑥𝐷)
84, 1, 5, 2, 7dchrf 25137 . . . . . 6 ((𝑁 ∈ ℕ ∧ (𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ 𝑥𝐷)) → 𝑥:(Base‘(ℤ/nℤ‘𝑁))⟶ℂ)
9 simprl 811 . . . . . 6 ((𝑁 ∈ ℕ ∧ (𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ 𝑥𝐷)) → 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)))
108, 9ffvelrnd 6511 . . . . 5 ((𝑁 ∈ ℕ ∧ (𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ 𝑥𝐷)) → (𝑥𝑎) ∈ ℂ)
113, 6, 10fsumcom 14677 . . . 4 (𝑁 ∈ ℕ → Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))Σ𝑥𝐷 (𝑥𝑎) = Σ𝑥𝐷 Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))(𝑥𝑎))
12 eqid 2748 . . . . . . 7 (1r‘(ℤ/nℤ‘𝑁)) = (1r‘(ℤ/nℤ‘𝑁))
13 simpl 474 . . . . . . 7 ((𝑁 ∈ ℕ ∧ 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))) → 𝑁 ∈ ℕ)
14 simpr 479 . . . . . . 7 ((𝑁 ∈ ℕ ∧ 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))) → 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)))
154, 5, 1, 12, 2, 13, 14sumdchr2 25165 . . . . . 6 ((𝑁 ∈ ℕ ∧ 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))) → Σ𝑥𝐷 (𝑥𝑎) = if(𝑎 = (1r‘(ℤ/nℤ‘𝑁)), (♯‘𝐷), 0))
16 velsn 4325 . . . . . . 7 (𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} ↔ 𝑎 = (1r‘(ℤ/nℤ‘𝑁)))
17 ifbi 4239 . . . . . . 7 ((𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} ↔ 𝑎 = (1r‘(ℤ/nℤ‘𝑁))) → if(𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))}, (♯‘𝐷), 0) = if(𝑎 = (1r‘(ℤ/nℤ‘𝑁)), (♯‘𝐷), 0))
1816, 17mp1i 13 . . . . . 6 ((𝑁 ∈ ℕ ∧ 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))) → if(𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))}, (♯‘𝐷), 0) = if(𝑎 = (1r‘(ℤ/nℤ‘𝑁)), (♯‘𝐷), 0))
1915, 18eqtr4d 2785 . . . . 5 ((𝑁 ∈ ℕ ∧ 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))) → Σ𝑥𝐷 (𝑥𝑎) = if(𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))}, (♯‘𝐷), 0))
2019sumeq2dv 14603 . . . 4 (𝑁 ∈ ℕ → Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))Σ𝑥𝐷 (𝑥𝑎) = Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))if(𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))}, (♯‘𝐷), 0))
21 eqid 2748 . . . . . . 7 (0g𝐺) = (0g𝐺)
22 simpr 479 . . . . . . 7 ((𝑁 ∈ ℕ ∧ 𝑥𝐷) → 𝑥𝐷)
234, 1, 5, 21, 22, 2dchrsum 25164 . . . . . 6 ((𝑁 ∈ ℕ ∧ 𝑥𝐷) → Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))(𝑥𝑎) = if(𝑥 = (0g𝐺), (ϕ‘𝑁), 0))
24 velsn 4325 . . . . . . 7 (𝑥 ∈ {(0g𝐺)} ↔ 𝑥 = (0g𝐺))
25 ifbi 4239 . . . . . . 7 ((𝑥 ∈ {(0g𝐺)} ↔ 𝑥 = (0g𝐺)) → if(𝑥 ∈ {(0g𝐺)}, (ϕ‘𝑁), 0) = if(𝑥 = (0g𝐺), (ϕ‘𝑁), 0))
2624, 25mp1i 13 . . . . . 6 ((𝑁 ∈ ℕ ∧ 𝑥𝐷) → if(𝑥 ∈ {(0g𝐺)}, (ϕ‘𝑁), 0) = if(𝑥 = (0g𝐺), (ϕ‘𝑁), 0))
2723, 26eqtr4d 2785 . . . . 5 ((𝑁 ∈ ℕ ∧ 𝑥𝐷) → Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))(𝑥𝑎) = if(𝑥 ∈ {(0g𝐺)}, (ϕ‘𝑁), 0))
2827sumeq2dv 14603 . . . 4 (𝑁 ∈ ℕ → Σ𝑥𝐷 Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))(𝑥𝑎) = Σ𝑥𝐷 if(𝑥 ∈ {(0g𝐺)}, (ϕ‘𝑁), 0))
2911, 20, 283eqtr3d 2790 . . 3 (𝑁 ∈ ℕ → Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))if(𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))}, (♯‘𝐷), 0) = Σ𝑥𝐷 if(𝑥 ∈ {(0g𝐺)}, (ϕ‘𝑁), 0))
30 nnnn0 11462 . . . . . 6 (𝑁 ∈ ℕ → 𝑁 ∈ ℕ0)
311zncrng 20066 . . . . . 6 (𝑁 ∈ ℕ0 → (ℤ/nℤ‘𝑁) ∈ CRing)
32 crngring 18729 . . . . . 6 ((ℤ/nℤ‘𝑁) ∈ CRing → (ℤ/nℤ‘𝑁) ∈ Ring)
332, 12ringidcl 18739 . . . . . 6 ((ℤ/nℤ‘𝑁) ∈ Ring → (1r‘(ℤ/nℤ‘𝑁)) ∈ (Base‘(ℤ/nℤ‘𝑁)))
3430, 31, 32, 334syl 19 . . . . 5 (𝑁 ∈ ℕ → (1r‘(ℤ/nℤ‘𝑁)) ∈ (Base‘(ℤ/nℤ‘𝑁)))
3534snssd 4473 . . . 4 (𝑁 ∈ ℕ → {(1r‘(ℤ/nℤ‘𝑁))} ⊆ (Base‘(ℤ/nℤ‘𝑁)))
36 hashcl 13310 . . . . . 6 (𝐷 ∈ Fin → (♯‘𝐷) ∈ ℕ0)
37 nn0cn 11465 . . . . . 6 ((♯‘𝐷) ∈ ℕ0 → (♯‘𝐷) ∈ ℂ)
386, 36, 373syl 18 . . . . 5 (𝑁 ∈ ℕ → (♯‘𝐷) ∈ ℂ)
3938ralrimivw 3093 . . . 4 (𝑁 ∈ ℕ → ∀𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) ∈ ℂ)
403olcd 407 . . . 4 (𝑁 ∈ ℕ → ((Base‘(ℤ/nℤ‘𝑁)) ⊆ (ℤ‘0) ∨ (Base‘(ℤ/nℤ‘𝑁)) ∈ Fin))
41 sumss2 14627 . . . 4 ((({(1r‘(ℤ/nℤ‘𝑁))} ⊆ (Base‘(ℤ/nℤ‘𝑁)) ∧ ∀𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) ∈ ℂ) ∧ ((Base‘(ℤ/nℤ‘𝑁)) ⊆ (ℤ‘0) ∨ (Base‘(ℤ/nℤ‘𝑁)) ∈ Fin)) → Σ𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) = Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))if(𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))}, (♯‘𝐷), 0))
4235, 39, 40, 41syl21anc 1462 . . 3 (𝑁 ∈ ℕ → Σ𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) = Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))if(𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))}, (♯‘𝐷), 0))
434dchrabl 25149 . . . . . 6 (𝑁 ∈ ℕ → 𝐺 ∈ Abel)
44 ablgrp 18369 . . . . . 6 (𝐺 ∈ Abel → 𝐺 ∈ Grp)
455, 21grpidcl 17622 . . . . . 6 (𝐺 ∈ Grp → (0g𝐺) ∈ 𝐷)
4643, 44, 453syl 18 . . . . 5 (𝑁 ∈ ℕ → (0g𝐺) ∈ 𝐷)
4746snssd 4473 . . . 4 (𝑁 ∈ ℕ → {(0g𝐺)} ⊆ 𝐷)
48 phicl 15647 . . . . . 6 (𝑁 ∈ ℕ → (ϕ‘𝑁) ∈ ℕ)
4948nncnd 11199 . . . . 5 (𝑁 ∈ ℕ → (ϕ‘𝑁) ∈ ℂ)
5049ralrimivw 3093 . . . 4 (𝑁 ∈ ℕ → ∀𝑥 ∈ {(0g𝐺)} (ϕ‘𝑁) ∈ ℂ)
516olcd 407 . . . 4 (𝑁 ∈ ℕ → (𝐷 ⊆ (ℤ‘0) ∨ 𝐷 ∈ Fin))
52 sumss2 14627 . . . 4 ((({(0g𝐺)} ⊆ 𝐷 ∧ ∀𝑥 ∈ {(0g𝐺)} (ϕ‘𝑁) ∈ ℂ) ∧ (𝐷 ⊆ (ℤ‘0) ∨ 𝐷 ∈ Fin)) → Σ𝑥 ∈ {(0g𝐺)} (ϕ‘𝑁) = Σ𝑥𝐷 if(𝑥 ∈ {(0g𝐺)}, (ϕ‘𝑁), 0))
5347, 50, 51, 52syl21anc 1462 . . 3 (𝑁 ∈ ℕ → Σ𝑥 ∈ {(0g𝐺)} (ϕ‘𝑁) = Σ𝑥𝐷 if(𝑥 ∈ {(0g𝐺)}, (ϕ‘𝑁), 0))
5429, 42, 533eqtr4d 2792 . 2 (𝑁 ∈ ℕ → Σ𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) = Σ𝑥 ∈ {(0g𝐺)} (ϕ‘𝑁))
55 eqidd 2749 . . . 4 (𝑎 = (1r‘(ℤ/nℤ‘𝑁)) → (♯‘𝐷) = (♯‘𝐷))
5655sumsn 14645 . . 3 (((1r‘(ℤ/nℤ‘𝑁)) ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ (♯‘𝐷) ∈ ℂ) → Σ𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) = (♯‘𝐷))
5734, 38, 56syl2anc 696 . 2 (𝑁 ∈ ℕ → Σ𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) = (♯‘𝐷))
58 eqidd 2749 . . . 4 (𝑥 = (0g𝐺) → (ϕ‘𝑁) = (ϕ‘𝑁))
5958sumsn 14645 . . 3 (((0g𝐺) ∈ 𝐷 ∧ (ϕ‘𝑁) ∈ ℂ) → Σ𝑥 ∈ {(0g𝐺)} (ϕ‘𝑁) = (ϕ‘𝑁))
6046, 49, 59syl2anc 696 . 2 (𝑁 ∈ ℕ → Σ𝑥 ∈ {(0g𝐺)} (ϕ‘𝑁) = (ϕ‘𝑁))
6154, 57, 603eqtr3d 2790 1 (𝑁 ∈ ℕ → (♯‘𝐷) = (ϕ‘𝑁))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 196  wo 382  wa 383   = wceq 1620  wcel 2127  wral 3038  wss 3703  ifcif 4218  {csn 4309  cfv 6037  Fincfn 8109  cc 10097  0cc0 10099  cn 11183  0cn0 11455  cuz 11850  chash 13282  Σcsu 14586  ϕcphi 15642  Basecbs 16030  0gc0g 16273  Grpcgrp 17594  Abelcabl 18365  1rcur 18672  Ringcrg 18718  CRingccrg 18719  ℤ/nczn 20024  DChrcdchr 25127
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1859  ax-4 1874  ax-5 1976  ax-6 2042  ax-7 2078  ax-8 2129  ax-9 2136  ax-10 2156  ax-11 2171  ax-12 2184  ax-13 2379  ax-ext 2728  ax-rep 4911  ax-sep 4921  ax-nul 4929  ax-pow 4980  ax-pr 5043  ax-un 7102  ax-inf2 8699  ax-cnex 10155  ax-resscn 10156  ax-1cn 10157  ax-icn 10158  ax-addcl 10159  ax-addrcl 10160  ax-mulcl 10161  ax-mulrcl 10162  ax-mulcom 10163  ax-addass 10164  ax-mulass 10165  ax-distr 10166  ax-i2m1 10167  ax-1ne0 10168  ax-1rid 10169  ax-rnegex 10170  ax-rrecex 10171  ax-cnre 10172  ax-pre-lttri 10173  ax-pre-lttrn 10174  ax-pre-ltadd 10175  ax-pre-mulgt0 10176  ax-pre-sup 10177  ax-addf 10178  ax-mulf 10179
This theorem depends on definitions:  df-bi 197  df-or 384  df-an 385  df-3or 1073  df-3an 1074  df-tru 1623  df-fal 1626  df-ex 1842  df-nf 1847  df-sb 2035  df-eu 2599  df-mo 2600  df-clab 2735  df-cleq 2741  df-clel 2744  df-nfc 2879  df-ne 2921  df-nel 3024  df-ral 3043  df-rex 3044  df-reu 3045  df-rmo 3046  df-rab 3047  df-v 3330  df-sbc 3565  df-csb 3663  df-dif 3706  df-un 3708  df-in 3710  df-ss 3717  df-pss 3719  df-nul 4047  df-if 4219  df-pw 4292  df-sn 4310  df-pr 4312  df-tp 4314  df-op 4316  df-uni 4577  df-int 4616  df-iun 4662  df-iin 4663  df-disj 4761  df-br 4793  df-opab 4853  df-mpt 4870  df-tr 4893  df-id 5162  df-eprel 5167  df-po 5175  df-so 5176  df-fr 5213  df-se 5214  df-we 5215  df-xp 5260  df-rel 5261  df-cnv 5262  df-co 5263  df-dm 5264  df-rn 5265  df-res 5266  df-ima 5267  df-pred 5829  df-ord 5875  df-on 5876  df-lim 5877  df-suc 5878  df-iota 6000  df-fun 6039  df-fn 6040  df-f 6041  df-f1 6042  df-fo 6043  df-f1o 6044  df-fv 6045  df-isom 6046  df-riota 6762  df-ov 6804  df-oprab 6805  df-mpt2 6806  df-of 7050  df-rpss 7090  df-om 7219  df-1st 7321  df-2nd 7322  df-supp 7452  df-tpos 7509  df-wrecs 7564  df-recs 7625  df-rdg 7663  df-1o 7717  df-2o 7718  df-oadd 7721  df-omul 7722  df-er 7899  df-ec 7901  df-qs 7905  df-map 8013  df-pm 8014  df-ixp 8063  df-en 8110  df-dom 8111  df-sdom 8112  df-fin 8113  df-fsupp 8429  df-fi 8470  df-sup 8501  df-inf 8502  df-oi 8568  df-card 8926  df-acn 8929  df-cda 9153  df-pnf 10239  df-mnf 10240  df-xr 10241  df-ltxr 10242  df-le 10243  df-sub 10431  df-neg 10432  df-div 10848  df-nn 11184  df-2 11242  df-3 11243  df-4 11244  df-5 11245  df-6 11246  df-7 11247  df-8 11248  df-9 11249  df-n0 11456  df-xnn0 11527  df-z 11541  df-dec 11657  df-uz 11851  df-q 11953  df-rp 11997  df-xneg 12110  df-xadd 12111  df-xmul 12112  df-ioo 12343  df-ioc 12344  df-ico 12345  df-icc 12346  df-fz 12491  df-fzo 12631  df-fl 12758  df-mod 12834  df-seq 12967  df-exp 13026  df-fac 13226  df-bc 13255  df-hash 13283  df-word 13456  df-concat 13458  df-s1 13459  df-shft 13977  df-cj 14009  df-re 14010  df-im 14011  df-sqrt 14145  df-abs 14146  df-limsup 14372  df-clim 14389  df-rlim 14390  df-sum 14587  df-ef 14968  df-sin 14970  df-cos 14971  df-pi 14973  df-dvds 15154  df-gcd 15390  df-prm 15559  df-phi 15644  df-pc 15715  df-struct 16032  df-ndx 16033  df-slot 16034  df-base 16036  df-sets 16037  df-ress 16038  df-plusg 16127  df-mulr 16128  df-starv 16129  df-sca 16130  df-vsca 16131  df-ip 16132  df-tset 16133  df-ple 16134  df-ds 16137  df-unif 16138  df-hom 16139  df-cco 16140  df-rest 16256  df-topn 16257  df-0g 16275  df-gsum 16276  df-topgen 16277  df-pt 16278  df-prds 16281  df-xrs 16335  df-qtop 16340  df-imas 16341  df-qus 16342  df-xps 16343  df-mre 16419  df-mrc 16420  df-acs 16422  df-mgm 17414  df-sgrp 17456  df-mnd 17467  df-mhm 17507  df-submnd 17508  df-grp 17597  df-minusg 17598  df-sbg 17599  df-mulg 17713  df-subg 17763  df-nsg 17764  df-eqg 17765  df-ghm 17830  df-gim 17873  df-ga 17894  df-cntz 17921  df-oppg 17947  df-od 18119  df-gex 18120  df-pgp 18121  df-lsm 18222  df-pj1 18223  df-cmn 18366  df-abl 18367  df-cyg 18451  df-dprd 18565  df-dpj 18566  df-mgp 18661  df-ur 18673  df-ring 18720  df-cring 18721  df-oppr 18794  df-dvdsr 18812  df-unit 18813  df-invr 18843  df-rnghom 18888  df-subrg 18951  df-lmod 19038  df-lss 19106  df-lsp 19145  df-sra 19345  df-rgmod 19346  df-lidl 19347  df-rsp 19348  df-2idl 19405  df-psmet 19911  df-xmet 19912  df-met 19913  df-bl 19914  df-mopn 19915  df-fbas 19916  df-fg 19917  df-cnfld 19920  df-zring 19992  df-zrh 20025  df-zn 20028  df-top 20872  df-topon 20889  df-topsp 20910  df-bases 20923  df-cld 20996  df-ntr 20997  df-cls 20998  df-nei 21075  df-lp 21113  df-perf 21114  df-cn 21204  df-cnp 21205  df-haus 21292  df-tx 21538  df-hmeo 21731  df-fil 21822  df-fm 21914  df-flim 21915  df-flf 21916  df-xms 22297  df-ms 22298  df-tms 22299  df-cncf 22853  df-0p 23607  df-limc 23800  df-dv 23801  df-ply 24114  df-idp 24115  df-coe 24116  df-dgr 24117  df-quot 24216  df-log 24473  df-cxp 24474  df-dchr 25128
This theorem is referenced by:  sumdchr  25167
  Copyright terms: Public domain W3C validator