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

Theorem dchrhash 27234
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 2737 . . . . . 6 (ℤ/nℤ‘𝑁) = (ℤ/nℤ‘𝑁)
2 eqid 2737 . . . . . 6 (Base‘(ℤ/nℤ‘𝑁)) = (Base‘(ℤ/nℤ‘𝑁))
31, 2znfi 21539 . . . . 5 (𝑁 ∈ ℕ → (Base‘(ℤ/nℤ‘𝑁)) ∈ Fin)
4 sumdchr.g . . . . . 6 𝐺 = (DChr‘𝑁)
5 sumdchr.d . . . . . 6 𝐷 = (Base‘𝐺)
64, 5dchrfi 27218 . . . . 5 (𝑁 ∈ ℕ → 𝐷 ∈ Fin)
7 simprr 773 . . . . . . 7 ((𝑁 ∈ ℕ ∧ (𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ 𝑥𝐷)) → 𝑥𝐷)
84, 1, 5, 2, 7dchrf 27205 . . . . . 6 ((𝑁 ∈ ℕ ∧ (𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ 𝑥𝐷)) → 𝑥:(Base‘(ℤ/nℤ‘𝑁))⟶ℂ)
9 simprl 771 . . . . . 6 ((𝑁 ∈ ℕ ∧ (𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ 𝑥𝐷)) → 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)))
108, 9ffvelcdmd 7038 . . . . 5 ((𝑁 ∈ ℕ ∧ (𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ 𝑥𝐷)) → (𝑥𝑎) ∈ ℂ)
113, 6, 10fsumcom 15737 . . . 4 (𝑁 ∈ ℕ → Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))Σ𝑥𝐷 (𝑥𝑎) = Σ𝑥𝐷 Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))(𝑥𝑎))
12 eqid 2737 . . . . . . 7 (1r‘(ℤ/nℤ‘𝑁)) = (1r‘(ℤ/nℤ‘𝑁))
13 simpl 482 . . . . . . 7 ((𝑁 ∈ ℕ ∧ 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))) → 𝑁 ∈ ℕ)
14 simpr 484 . . . . . . 7 ((𝑁 ∈ ℕ ∧ 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))) → 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)))
154, 5, 1, 12, 2, 13, 14sumdchr2 27233 . . . . . 6 ((𝑁 ∈ ℕ ∧ 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))) → Σ𝑥𝐷 (𝑥𝑎) = if(𝑎 = (1r‘(ℤ/nℤ‘𝑁)), (♯‘𝐷), 0))
16 velsn 4584 . . . . . . 7 (𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} ↔ 𝑎 = (1r‘(ℤ/nℤ‘𝑁)))
17 ifbi 4490 . . . . . . 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 2775 . . . . 5 ((𝑁 ∈ ℕ ∧ 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))) → Σ𝑥𝐷 (𝑥𝑎) = if(𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))}, (♯‘𝐷), 0))
2019sumeq2dv 15664 . . . 4 (𝑁 ∈ ℕ → Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))Σ𝑥𝐷 (𝑥𝑎) = Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))if(𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))}, (♯‘𝐷), 0))
21 eqid 2737 . . . . . . 7 (0g𝐺) = (0g𝐺)
22 simpr 484 . . . . . . 7 ((𝑁 ∈ ℕ ∧ 𝑥𝐷) → 𝑥𝐷)
234, 1, 5, 21, 22, 2dchrsum 27232 . . . . . 6 ((𝑁 ∈ ℕ ∧ 𝑥𝐷) → Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))(𝑥𝑎) = if(𝑥 = (0g𝐺), (ϕ‘𝑁), 0))
24 velsn 4584 . . . . . . 7 (𝑥 ∈ {(0g𝐺)} ↔ 𝑥 = (0g𝐺))
25 ifbi 4490 . . . . . . 7 ((𝑥 ∈ {(0g𝐺)} ↔ 𝑥 = (0g𝐺)) → if(𝑥 ∈ {(0g𝐺)}, (ϕ‘𝑁), 0) = if(𝑥 = (0g𝐺), (ϕ‘𝑁), 0))
2624, 25mp1i 13 . . . . . 6 ((𝑁 ∈ ℕ ∧ 𝑥𝐷) → if(𝑥 ∈ {(0g𝐺)}, (ϕ‘𝑁), 0) = if(𝑥 = (0g𝐺), (ϕ‘𝑁), 0))
2723, 26eqtr4d 2775 . . . . 5 ((𝑁 ∈ ℕ ∧ 𝑥𝐷) → Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))(𝑥𝑎) = if(𝑥 ∈ {(0g𝐺)}, (ϕ‘𝑁), 0))
2827sumeq2dv 15664 . . . 4 (𝑁 ∈ ℕ → Σ𝑥𝐷 Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))(𝑥𝑎) = Σ𝑥𝐷 if(𝑥 ∈ {(0g𝐺)}, (ϕ‘𝑁), 0))
2911, 20, 283eqtr3d 2780 . . 3 (𝑁 ∈ ℕ → Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))if(𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))}, (♯‘𝐷), 0) = Σ𝑥𝐷 if(𝑥 ∈ {(0g𝐺)}, (ϕ‘𝑁), 0))
30 nnnn0 12444 . . . . . 6 (𝑁 ∈ ℕ → 𝑁 ∈ ℕ0)
311zncrng 21524 . . . . . 6 (𝑁 ∈ ℕ0 → (ℤ/nℤ‘𝑁) ∈ CRing)
32 crngring 20226 . . . . . 6 ((ℤ/nℤ‘𝑁) ∈ CRing → (ℤ/nℤ‘𝑁) ∈ Ring)
332, 12ringidcl 20246 . . . . . 6 ((ℤ/nℤ‘𝑁) ∈ Ring → (1r‘(ℤ/nℤ‘𝑁)) ∈ (Base‘(ℤ/nℤ‘𝑁)))
3430, 31, 32, 334syl 19 . . . . 5 (𝑁 ∈ ℕ → (1r‘(ℤ/nℤ‘𝑁)) ∈ (Base‘(ℤ/nℤ‘𝑁)))
3534snssd 4731 . . . 4 (𝑁 ∈ ℕ → {(1r‘(ℤ/nℤ‘𝑁))} ⊆ (Base‘(ℤ/nℤ‘𝑁)))
36 hashcl 14318 . . . . . 6 (𝐷 ∈ Fin → (♯‘𝐷) ∈ ℕ0)
37 nn0cn 12447 . . . . . 6 ((♯‘𝐷) ∈ ℕ0 → (♯‘𝐷) ∈ ℂ)
386, 36, 373syl 18 . . . . 5 (𝑁 ∈ ℕ → (♯‘𝐷) ∈ ℂ)
3938ralrimivw 3134 . . . 4 (𝑁 ∈ ℕ → ∀𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) ∈ ℂ)
403olcd 875 . . . 4 (𝑁 ∈ ℕ → ((Base‘(ℤ/nℤ‘𝑁)) ⊆ (ℤ‘0) ∨ (Base‘(ℤ/nℤ‘𝑁)) ∈ Fin))
41 sumss2 15688 . . . 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 838 . . 3 (𝑁 ∈ ℕ → Σ𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) = Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))if(𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))}, (♯‘𝐷), 0))
434dchrabl 27217 . . . . . 6 (𝑁 ∈ ℕ → 𝐺 ∈ Abel)
44 ablgrp 19760 . . . . . 6 (𝐺 ∈ Abel → 𝐺 ∈ Grp)
455, 21grpidcl 18941 . . . . . 6 (𝐺 ∈ Grp → (0g𝐺) ∈ 𝐷)
4643, 44, 453syl 18 . . . . 5 (𝑁 ∈ ℕ → (0g𝐺) ∈ 𝐷)
4746snssd 4731 . . . 4 (𝑁 ∈ ℕ → {(0g𝐺)} ⊆ 𝐷)
48 phicl 16739 . . . . . 6 (𝑁 ∈ ℕ → (ϕ‘𝑁) ∈ ℕ)
4948nncnd 12190 . . . . 5 (𝑁 ∈ ℕ → (ϕ‘𝑁) ∈ ℂ)
5049ralrimivw 3134 . . . 4 (𝑁 ∈ ℕ → ∀𝑥 ∈ {(0g𝐺)} (ϕ‘𝑁) ∈ ℂ)
516olcd 875 . . . 4 (𝑁 ∈ ℕ → (𝐷 ⊆ (ℤ‘0) ∨ 𝐷 ∈ Fin))
52 sumss2 15688 . . . 4 ((({(0g𝐺)} ⊆ 𝐷 ∧ ∀𝑥 ∈ {(0g𝐺)} (ϕ‘𝑁) ∈ ℂ) ∧ (𝐷 ⊆ (ℤ‘0) ∨ 𝐷 ∈ Fin)) → Σ𝑥 ∈ {(0g𝐺)} (ϕ‘𝑁) = Σ𝑥𝐷 if(𝑥 ∈ {(0g𝐺)}, (ϕ‘𝑁), 0))
5347, 50, 51, 52syl21anc 838 . . 3 (𝑁 ∈ ℕ → Σ𝑥 ∈ {(0g𝐺)} (ϕ‘𝑁) = Σ𝑥𝐷 if(𝑥 ∈ {(0g𝐺)}, (ϕ‘𝑁), 0))
5429, 42, 533eqtr4d 2782 . 2 (𝑁 ∈ ℕ → Σ𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) = Σ𝑥 ∈ {(0g𝐺)} (ϕ‘𝑁))
55 eqidd 2738 . . . 4 (𝑎 = (1r‘(ℤ/nℤ‘𝑁)) → (♯‘𝐷) = (♯‘𝐷))
5655sumsn 15708 . . 3 (((1r‘(ℤ/nℤ‘𝑁)) ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ (♯‘𝐷) ∈ ℂ) → Σ𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) = (♯‘𝐷))
5734, 38, 56syl2anc 585 . 2 (𝑁 ∈ ℕ → Σ𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) = (♯‘𝐷))
58 eqidd 2738 . . . 4 (𝑥 = (0g𝐺) → (ϕ‘𝑁) = (ϕ‘𝑁))
5958sumsn 15708 . . 3 (((0g𝐺) ∈ 𝐷 ∧ (ϕ‘𝑁) ∈ ℂ) → Σ𝑥 ∈ {(0g𝐺)} (ϕ‘𝑁) = (ϕ‘𝑁))
6046, 49, 59syl2anc 585 . 2 (𝑁 ∈ ℕ → Σ𝑥 ∈ {(0g𝐺)} (ϕ‘𝑁) = (ϕ‘𝑁))
6154, 57, 603eqtr3d 2780 1 (𝑁 ∈ ℕ → (♯‘𝐷) = (ϕ‘𝑁))
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 206  wa 395  wo 848   = wceq 1542  wcel 2114  wral 3052  wss 3890  ifcif 4467  {csn 4568  cfv 6499  Fincfn 8893  cc 11036  0cc0 11038  cn 12174  0cn0 12437  cuz 12788  chash 14292  Σcsu 15648  ϕcphi 16734  Basecbs 17179  0gc0g 17402  Grpcgrp 18909  Abelcabl 19756  1rcur 20162  Ringcrg 20214  CRingccrg 20215  ℤ/nczn 21482  DChrcdchr 27195
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1797  ax-4 1811  ax-5 1912  ax-6 1969  ax-7 2010  ax-8 2116  ax-9 2124  ax-10 2147  ax-11 2163  ax-12 2185  ax-ext 2709  ax-rep 5213  ax-sep 5232  ax-nul 5242  ax-pow 5308  ax-pr 5376  ax-un 7689  ax-inf2 9562  ax-cnex 11094  ax-resscn 11095  ax-1cn 11096  ax-icn 11097  ax-addcl 11098  ax-addrcl 11099  ax-mulcl 11100  ax-mulrcl 11101  ax-mulcom 11102  ax-addass 11103  ax-mulass 11104  ax-distr 11105  ax-i2m1 11106  ax-1ne0 11107  ax-1rid 11108  ax-rnegex 11109  ax-rrecex 11110  ax-cnre 11111  ax-pre-lttri 11112  ax-pre-lttrn 11113  ax-pre-ltadd 11114  ax-pre-mulgt0 11115  ax-pre-sup 11116  ax-addf 11117  ax-mulf 11118
This theorem depends on definitions:  df-bi 207  df-an 396  df-or 849  df-3or 1088  df-3an 1089  df-tru 1545  df-fal 1555  df-ex 1782  df-nf 1786  df-sb 2069  df-mo 2540  df-eu 2570  df-clab 2716  df-cleq 2729  df-clel 2812  df-nfc 2886  df-ne 2934  df-nel 3038  df-ral 3053  df-rex 3063  df-rmo 3343  df-reu 3344  df-rab 3391  df-v 3432  df-sbc 3730  df-csb 3839  df-dif 3893  df-un 3895  df-in 3897  df-ss 3907  df-pss 3910  df-nul 4275  df-if 4468  df-pw 4544  df-sn 4569  df-pr 4571  df-tp 4573  df-op 4575  df-uni 4852  df-int 4891  df-iun 4936  df-iin 4937  df-disj 5054  df-br 5087  df-opab 5149  df-mpt 5168  df-tr 5194  df-id 5526  df-eprel 5531  df-po 5539  df-so 5540  df-fr 5584  df-se 5585  df-we 5586  df-xp 5637  df-rel 5638  df-cnv 5639  df-co 5640  df-dm 5641  df-rn 5642  df-res 5643  df-ima 5644  df-pred 6266  df-ord 6327  df-on 6328  df-lim 6329  df-suc 6330  df-iota 6455  df-fun 6501  df-fn 6502  df-f 6503  df-f1 6504  df-fo 6505  df-f1o 6506  df-fv 6507  df-isom 6508  df-riota 7324  df-ov 7370  df-oprab 7371  df-mpo 7372  df-of 7631  df-rpss 7677  df-om 7818  df-1st 7942  df-2nd 7943  df-supp 8111  df-tpos 8176  df-frecs 8231  df-wrecs 8262  df-recs 8311  df-rdg 8349  df-1o 8405  df-2o 8406  df-oadd 8409  df-omul 8410  df-er 8643  df-ec 8645  df-qs 8649  df-map 8775  df-pm 8776  df-ixp 8846  df-en 8894  df-dom 8895  df-sdom 8896  df-fin 8897  df-fsupp 9275  df-fi 9324  df-sup 9355  df-inf 9356  df-oi 9425  df-dju 9825  df-card 9863  df-acn 9866  df-pnf 11181  df-mnf 11182  df-xr 11183  df-ltxr 11184  df-le 11185  df-sub 11379  df-neg 11380  df-div 11808  df-nn 12175  df-2 12244  df-3 12245  df-4 12246  df-5 12247  df-6 12248  df-7 12249  df-8 12250  df-9 12251  df-n0 12438  df-xnn0 12511  df-z 12525  df-dec 12645  df-uz 12789  df-q 12899  df-rp 12943  df-xneg 13063  df-xadd 13064  df-xmul 13065  df-ioo 13302  df-ioc 13303  df-ico 13304  df-icc 13305  df-fz 13462  df-fzo 13609  df-fl 13751  df-mod 13829  df-seq 13964  df-exp 14024  df-fac 14236  df-bc 14265  df-hash 14293  df-word 14476  df-concat 14533  df-s1 14559  df-shft 15029  df-cj 15061  df-re 15062  df-im 15063  df-sqrt 15197  df-abs 15198  df-limsup 15433  df-clim 15450  df-rlim 15451  df-sum 15649  df-ef 16032  df-sin 16034  df-cos 16035  df-pi 16037  df-dvds 16222  df-gcd 16464  df-prm 16641  df-phi 16736  df-pc 16808  df-struct 17117  df-sets 17134  df-slot 17152  df-ndx 17164  df-base 17180  df-ress 17201  df-plusg 17233  df-mulr 17234  df-starv 17235  df-sca 17236  df-vsca 17237  df-ip 17238  df-tset 17239  df-ple 17240  df-ds 17242  df-unif 17243  df-hom 17244  df-cco 17245  df-rest 17385  df-topn 17386  df-0g 17404  df-gsum 17405  df-topgen 17406  df-pt 17407  df-prds 17410  df-xrs 17466  df-qtop 17471  df-imas 17472  df-qus 17473  df-xps 17474  df-mre 17548  df-mrc 17549  df-acs 17551  df-mgm 18608  df-sgrp 18687  df-mnd 18703  df-mhm 18751  df-submnd 18752  df-grp 18912  df-minusg 18913  df-sbg 18914  df-mulg 19044  df-subg 19099  df-nsg 19100  df-eqg 19101  df-ghm 19188  df-gim 19234  df-ga 19265  df-cntz 19292  df-oppg 19321  df-od 19503  df-gex 19504  df-pgp 19505  df-lsm 19611  df-pj1 19612  df-cmn 19757  df-abl 19758  df-cyg 19853  df-dprd 19972  df-dpj 19973  df-mgp 20122  df-rng 20134  df-ur 20163  df-ring 20216  df-cring 20217  df-oppr 20317  df-dvdsr 20337  df-unit 20338  df-invr 20368  df-rhm 20452  df-subrng 20523  df-subrg 20547  df-lmod 20857  df-lss 20927  df-lsp 20967  df-sra 21168  df-rgmod 21169  df-lidl 21206  df-rsp 21207  df-2idl 21248  df-psmet 21344  df-xmet 21345  df-met 21346  df-bl 21347  df-mopn 21348  df-fbas 21349  df-fg 21350  df-cnfld 21353  df-zring 21427  df-zrh 21483  df-zn 21486  df-top 22859  df-topon 22876  df-topsp 22898  df-bases 22911  df-cld 22984  df-ntr 22985  df-cls 22986  df-nei 23063  df-lp 23101  df-perf 23102  df-cn 23192  df-cnp 23193  df-haus 23280  df-tx 23527  df-hmeo 23720  df-fil 23811  df-fm 23903  df-flim 23904  df-flf 23905  df-xms 24285  df-ms 24286  df-tms 24287  df-cncf 24845  df-0p 25637  df-limc 25833  df-dv 25834  df-ply 26153  df-idp 26154  df-coe 26155  df-dgr 26156  df-quot 26257  df-log 26520  df-cxp 26521  df-dchr 27196
This theorem is referenced by:  sumdchr  27235
  Copyright terms: Public domain W3C validator