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

Theorem dchrhash 27222
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 21516 . . . . 5 (𝑁 ∈ ℕ → (Base‘(ℤ/nℤ‘𝑁)) ∈ Fin)
4 sumdchr.g . . . . . 6 𝐺 = (DChr‘𝑁)
5 sumdchr.d . . . . . 6 𝐷 = (Base‘𝐺)
64, 5dchrfi 27206 . . . . 5 (𝑁 ∈ ℕ → 𝐷 ∈ Fin)
7 simprr 773 . . . . . . 7 ((𝑁 ∈ ℕ ∧ (𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ 𝑥𝐷)) → 𝑥𝐷)
84, 1, 5, 2, 7dchrf 27193 . . . . . 6 ((𝑁 ∈ ℕ ∧ (𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ 𝑥𝐷)) → 𝑥:(Base‘(ℤ/nℤ‘𝑁))⟶ℂ)
9 simprl 771 . . . . . 6 ((𝑁 ∈ ℕ ∧ (𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ 𝑥𝐷)) → 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)))
108, 9ffvelcdmd 7029 . . . . 5 ((𝑁 ∈ ℕ ∧ (𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ 𝑥𝐷)) → (𝑥𝑎) ∈ ℂ)
113, 6, 10fsumcom 15699 . . . 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 27221 . . . . . 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 15626 . . . 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 27220 . . . . . 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 15626 . . . 4 (𝑁 ∈ ℕ → Σ𝑥𝐷 Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))(𝑥𝑎) = Σ𝑥𝐷 if(𝑥 ∈ {(0g𝐺)}, (ϕ‘𝑁), 0))
2911, 20, 283eqtr3d 2780 . . 3 (𝑁 ∈ ℕ → Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))if(𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))}, (♯‘𝐷), 0) = Σ𝑥𝐷 if(𝑥 ∈ {(0g𝐺)}, (ϕ‘𝑁), 0))
30 nnnn0 12409 . . . . . 6 (𝑁 ∈ ℕ → 𝑁 ∈ ℕ0)
311zncrng 21501 . . . . . 6 (𝑁 ∈ ℕ0 → (ℤ/nℤ‘𝑁) ∈ CRing)
32 crngring 20184 . . . . . 6 ((ℤ/nℤ‘𝑁) ∈ CRing → (ℤ/nℤ‘𝑁) ∈ Ring)
332, 12ringidcl 20204 . . . . . 6 ((ℤ/nℤ‘𝑁) ∈ Ring → (1r‘(ℤ/nℤ‘𝑁)) ∈ (Base‘(ℤ/nℤ‘𝑁)))
3430, 31, 32, 334syl 19 . . . . 5 (𝑁 ∈ ℕ → (1r‘(ℤ/nℤ‘𝑁)) ∈ (Base‘(ℤ/nℤ‘𝑁)))
3534snssd 4753 . . . 4 (𝑁 ∈ ℕ → {(1r‘(ℤ/nℤ‘𝑁))} ⊆ (Base‘(ℤ/nℤ‘𝑁)))
36 hashcl 14280 . . . . . 6 (𝐷 ∈ Fin → (♯‘𝐷) ∈ ℕ0)
37 nn0cn 12412 . . . . . 6 ((♯‘𝐷) ∈ ℕ0 → (♯‘𝐷) ∈ ℂ)
386, 36, 373syl 18 . . . . 5 (𝑁 ∈ ℕ → (♯‘𝐷) ∈ ℂ)
3938ralrimivw 3134 . . . 4 (𝑁 ∈ ℕ → ∀𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) ∈ ℂ)
403olcd 875 . . . 4 (𝑁 ∈ ℕ → ((Base‘(ℤ/nℤ‘𝑁)) ⊆ (ℤ‘0) ∨ (Base‘(ℤ/nℤ‘𝑁)) ∈ Fin))
41 sumss2 15650 . . . 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 27205 . . . . . 6 (𝑁 ∈ ℕ → 𝐺 ∈ Abel)
44 ablgrp 19718 . . . . . 6 (𝐺 ∈ Abel → 𝐺 ∈ Grp)
455, 21grpidcl 18899 . . . . . 6 (𝐺 ∈ Grp → (0g𝐺) ∈ 𝐷)
4643, 44, 453syl 18 . . . . 5 (𝑁 ∈ ℕ → (0g𝐺) ∈ 𝐷)
4746snssd 4753 . . . 4 (𝑁 ∈ ℕ → {(0g𝐺)} ⊆ 𝐷)
48 phicl 16697 . . . . . 6 (𝑁 ∈ ℕ → (ϕ‘𝑁) ∈ ℕ)
4948nncnd 12162 . . . . 5 (𝑁 ∈ ℕ → (ϕ‘𝑁) ∈ ℂ)
5049ralrimivw 3134 . . . 4 (𝑁 ∈ ℕ → ∀𝑥 ∈ {(0g𝐺)} (ϕ‘𝑁) ∈ ℂ)
516olcd 875 . . . 4 (𝑁 ∈ ℕ → (𝐷 ⊆ (ℤ‘0) ∨ 𝐷 ∈ Fin))
52 sumss2 15650 . . . 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 15670 . . 3 (((1r‘(ℤ/nℤ‘𝑁)) ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ (♯‘𝐷) ∈ ℂ) → Σ𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) = (♯‘𝐷))
5734, 38, 56syl2anc 585 . 2 (𝑁 ∈ ℕ → Σ𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) = (♯‘𝐷))
58 eqidd 2738 . . . 4 (𝑥 = (0g𝐺) → (ϕ‘𝑁) = (ϕ‘𝑁))
5958sumsn 15670 . . 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 6490  Fincfn 8884  cc 11025  0cc0 11027  cn 12146  0cn0 12402  cuz 12752  chash 14254  Σcsu 15610  ϕcphi 16692  Basecbs 17137  0gc0g 17360  Grpcgrp 18867  Abelcabl 19714  1rcur 20120  Ringcrg 20172  CRingccrg 20173  ℤ/nczn 21459  DChrcdchr 27183
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 5212  ax-sep 5231  ax-nul 5241  ax-pow 5300  ax-pr 5368  ax-un 7680  ax-inf2 9551  ax-cnex 11083  ax-resscn 11084  ax-1cn 11085  ax-icn 11086  ax-addcl 11087  ax-addrcl 11088  ax-mulcl 11089  ax-mulrcl 11090  ax-mulcom 11091  ax-addass 11092  ax-mulass 11093  ax-distr 11094  ax-i2m1 11095  ax-1ne0 11096  ax-1rid 11097  ax-rnegex 11098  ax-rrecex 11099  ax-cnre 11100  ax-pre-lttri 11101  ax-pre-lttrn 11102  ax-pre-ltadd 11103  ax-pre-mulgt0 11104  ax-pre-sup 11105  ax-addf 11106  ax-mulf 11107
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 5517  df-eprel 5522  df-po 5530  df-so 5531  df-fr 5575  df-se 5576  df-we 5577  df-xp 5628  df-rel 5629  df-cnv 5630  df-co 5631  df-dm 5632  df-rn 5633  df-res 5634  df-ima 5635  df-pred 6257  df-ord 6318  df-on 6319  df-lim 6320  df-suc 6321  df-iota 6446  df-fun 6492  df-fn 6493  df-f 6494  df-f1 6495  df-fo 6496  df-f1o 6497  df-fv 6498  df-isom 6499  df-riota 7315  df-ov 7361  df-oprab 7362  df-mpo 7363  df-of 7622  df-rpss 7668  df-om 7809  df-1st 7933  df-2nd 7934  df-supp 8102  df-tpos 8167  df-frecs 8222  df-wrecs 8253  df-recs 8302  df-rdg 8340  df-1o 8396  df-2o 8397  df-oadd 8400  df-omul 8401  df-er 8634  df-ec 8636  df-qs 8640  df-map 8766  df-pm 8767  df-ixp 8837  df-en 8885  df-dom 8886  df-sdom 8887  df-fin 8888  df-fsupp 9266  df-fi 9315  df-sup 9346  df-inf 9347  df-oi 9416  df-dju 9814  df-card 9852  df-acn 9855  df-pnf 11169  df-mnf 11170  df-xr 11171  df-ltxr 11172  df-le 11173  df-sub 11367  df-neg 11368  df-div 11796  df-nn 12147  df-2 12209  df-3 12210  df-4 12211  df-5 12212  df-6 12213  df-7 12214  df-8 12215  df-9 12216  df-n0 12403  df-xnn0 12476  df-z 12490  df-dec 12609  df-uz 12753  df-q 12863  df-rp 12907  df-xneg 13027  df-xadd 13028  df-xmul 13029  df-ioo 13266  df-ioc 13267  df-ico 13268  df-icc 13269  df-fz 13425  df-fzo 13572  df-fl 13713  df-mod 13791  df-seq 13926  df-exp 13986  df-fac 14198  df-bc 14227  df-hash 14255  df-word 14438  df-concat 14495  df-s1 14521  df-shft 14991  df-cj 15023  df-re 15024  df-im 15025  df-sqrt 15159  df-abs 15160  df-limsup 15395  df-clim 15412  df-rlim 15413  df-sum 15611  df-ef 15991  df-sin 15993  df-cos 15994  df-pi 15996  df-dvds 16181  df-gcd 16423  df-prm 16600  df-phi 16694  df-pc 16766  df-struct 17075  df-sets 17092  df-slot 17110  df-ndx 17122  df-base 17138  df-ress 17159  df-plusg 17191  df-mulr 17192  df-starv 17193  df-sca 17194  df-vsca 17195  df-ip 17196  df-tset 17197  df-ple 17198  df-ds 17200  df-unif 17201  df-hom 17202  df-cco 17203  df-rest 17343  df-topn 17344  df-0g 17362  df-gsum 17363  df-topgen 17364  df-pt 17365  df-prds 17368  df-xrs 17424  df-qtop 17429  df-imas 17430  df-qus 17431  df-xps 17432  df-mre 17506  df-mrc 17507  df-acs 17509  df-mgm 18566  df-sgrp 18645  df-mnd 18661  df-mhm 18709  df-submnd 18710  df-grp 18870  df-minusg 18871  df-sbg 18872  df-mulg 19002  df-subg 19057  df-nsg 19058  df-eqg 19059  df-ghm 19146  df-gim 19192  df-ga 19223  df-cntz 19250  df-oppg 19279  df-od 19461  df-gex 19462  df-pgp 19463  df-lsm 19569  df-pj1 19570  df-cmn 19715  df-abl 19716  df-cyg 19811  df-dprd 19930  df-dpj 19931  df-mgp 20080  df-rng 20092  df-ur 20121  df-ring 20174  df-cring 20175  df-oppr 20275  df-dvdsr 20295  df-unit 20296  df-invr 20326  df-rhm 20410  df-subrng 20481  df-subrg 20505  df-lmod 20815  df-lss 20885  df-lsp 20925  df-sra 21127  df-rgmod 21128  df-lidl 21165  df-rsp 21166  df-2idl 21207  df-psmet 21303  df-xmet 21304  df-met 21305  df-bl 21306  df-mopn 21307  df-fbas 21308  df-fg 21309  df-cnfld 21312  df-zring 21404  df-zrh 21460  df-zn 21463  df-top 22837  df-topon 22854  df-topsp 22876  df-bases 22889  df-cld 22962  df-ntr 22963  df-cls 22964  df-nei 23041  df-lp 23079  df-perf 23080  df-cn 23170  df-cnp 23171  df-haus 23258  df-tx 23505  df-hmeo 23698  df-fil 23789  df-fm 23881  df-flim 23882  df-flf 23883  df-xms 24263  df-ms 24264  df-tms 24265  df-cncf 24823  df-0p 25615  df-limc 25811  df-dv 25812  df-ply 26134  df-idp 26135  df-coe 26136  df-dgr 26137  df-quot 26239  df-log 26505  df-cxp 26506  df-dchr 27184
This theorem is referenced by:  sumdchr  27223
  Copyright terms: Public domain W3C validator