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

Theorem dchrhash 27561
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 2760 . . . . . 6 (ℤ/nℤ‘𝑁) = (ℤ/nℤ‘𝑁)
2 eqid 2760 . . . . . 6 (Base‘(ℤ/nℤ‘𝑁)) = (Base‘(ℤ/nℤ‘𝑁))
31, 2znfi 21826 . . . . 5 (𝑁 ∈ ℕ → (Base‘(ℤ/nℤ‘𝑁)) ∈ Fin)
4 sumdchr.g . . . . . 6 𝐺 = (DChr‘𝑁)
5 sumdchr.d . . . . . 6 𝐷 = (Base‘𝐺)
64, 5dchrfi 27545 . . . . 5 (𝑁 ∈ ℕ → 𝐷 ∈ Fin)
7 simprr 785 . . . . . . 7 ((𝑁 ∈ ℕ ∧ (𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ 𝑥 ∈ 𝐷)) → 𝑥 ∈ 𝐷)
84, 1, 5, 2, 7dchrf 27532 . . . . . 6 ((𝑁 ∈ ℕ ∧ (𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ 𝑥 ∈ 𝐷)) → 𝑥:(Base‘(ℤ/nℤ‘𝑁))⟶ℂ)
9 simprl 783 . . . . . 6 ((𝑁 ∈ ℕ ∧ (𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ 𝑥 ∈ 𝐷)) → 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)))
108, 9ffvelcdmd 7073 . . . . 5 ((𝑁 ∈ ℕ ∧ (𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ 𝑥 ∈ 𝐷)) → (𝑥‘𝑎) ∈ ℂ)
113, 6, 10fsumcom 15908 . . . 4 (𝑁 ∈ ℕ → Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))Σ𝑥 ∈ 𝐷 (𝑥‘𝑎) = Σ𝑥 ∈ 𝐷 Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))(𝑥‘𝑎))
12 eqid 2760 . . . . . . 7 (1r‘(ℤ/nℤ‘𝑁)) = (1r‘(ℤ/nℤ‘𝑁))
13 simpl 488 . . . . . . 7 ((𝑁 ∈ ℕ ∧ 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))) → 𝑁 ∈ ℕ)
14 simpr 490 . . . . . . 7 ((𝑁 ∈ ℕ ∧ 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))) → 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁)))
154, 5, 1, 12, 2, 13, 14sumdchr2 27560 . . . . . 6 ((𝑁 ∈ ℕ ∧ 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))) → Σ𝑥 ∈ 𝐷 (𝑥‘𝑎) = if(𝑎 = (1r‘(ℤ/nℤ‘𝑁)), (♯‘𝐷), 0))
16 velsn 4599 . . . . . . 7 (𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} ↔ 𝑎 = (1r‘(ℤ/nℤ‘𝑁)))
17 ifbi 4504 . . . . . . 7 ((𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} ↔ 𝑎 = (1r‘(ℤ/nℤ‘𝑁))) → if(𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))}, (♯‘𝐷), 0) = if(𝑎 = (1r‘(ℤ/nℤ‘𝑁)), (♯‘𝐷), 0))
1816, 17mp1i 14 . . . . . 6 ((𝑁 ∈ ℕ ∧ 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))) → if(𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))}, (♯‘𝐷), 0) = if(𝑎 = (1r‘(ℤ/nℤ‘𝑁)), (♯‘𝐷), 0))
1915, 18eqtr4d 2798 . . . . 5 ((𝑁 ∈ ℕ ∧ 𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))) → Σ𝑥 ∈ 𝐷 (𝑥‘𝑎) = if(𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))}, (♯‘𝐷), 0))
2019sumeq2dv 15836 . . . 4 (𝑁 ∈ ℕ → Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))Σ𝑥 ∈ 𝐷 (𝑥‘𝑎) = Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))if(𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))}, (♯‘𝐷), 0))
21 eqid 2760 . . . . . . 7 (0g‘𝐺) = (0g‘𝐺)
22 simpr 490 . . . . . . 7 ((𝑁 ∈ ℕ ∧ 𝑥 ∈ 𝐷) → 𝑥 ∈ 𝐷)
234, 1, 5, 21, 22, 2dchrsum 27559 . . . . . 6 ((𝑁 ∈ ℕ ∧ 𝑥 ∈ 𝐷) → Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))(𝑥‘𝑎) = if(𝑥 = (0g‘𝐺), (ϕ‘𝑁), 0))
24 velsn 4599 . . . . . . 7 (𝑥 ∈ {(0g‘𝐺)} ↔ 𝑥 = (0g‘𝐺))
25 ifbi 4504 . . . . . . 7 ((𝑥 ∈ {(0g‘𝐺)} ↔ 𝑥 = (0g‘𝐺)) → if(𝑥 ∈ {(0g‘𝐺)}, (ϕ‘𝑁), 0) = if(𝑥 = (0g‘𝐺), (ϕ‘𝑁), 0))
2624, 25mp1i 14 . . . . . 6 ((𝑁 ∈ ℕ ∧ 𝑥 ∈ 𝐷) → if(𝑥 ∈ {(0g‘𝐺)}, (ϕ‘𝑁), 0) = if(𝑥 = (0g‘𝐺), (ϕ‘𝑁), 0))
2723, 26eqtr4d 2798 . . . . 5 ((𝑁 ∈ ℕ ∧ 𝑥 ∈ 𝐷) → Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))(𝑥‘𝑎) = if(𝑥 ∈ {(0g‘𝐺)}, (ϕ‘𝑁), 0))
2827sumeq2dv 15836 . . . 4 (𝑁 ∈ ℕ → Σ𝑥 ∈ 𝐷 Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))(𝑥‘𝑎) = Σ𝑥 ∈ 𝐷 if(𝑥 ∈ {(0g‘𝐺)}, (ϕ‘𝑁), 0))
2911, 20, 283eqtr3d 2803 . . 3 (𝑁 ∈ ℕ → Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))if(𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))}, (♯‘𝐷), 0) = Σ𝑥 ∈ 𝐷 if(𝑥 ∈ {(0g‘𝐺)}, (ϕ‘𝑁), 0))
30 nnnn0 12582 . . . . . 6 (𝑁 ∈ ℕ → 𝑁 ∈ ℕ0)
311zncrng 21811 . . . . . 6 (𝑁 ∈ ℕ0 → (ℤ/nℤ‘𝑁) ∈ CRing)
32 crngring 20433 . . . . . 6 ((ℤ/nℤ‘𝑁) ∈ CRing → (ℤ/nℤ‘𝑁) ∈ Ring)
332, 12ringidcl 20455 . . . . . 6 ((ℤ/nℤ‘𝑁) ∈ Ring → (1r‘(ℤ/nℤ‘𝑁)) ∈ (Base‘(ℤ/nℤ‘𝑁)))
3430, 31, 32, 334syl 20 . . . . 5 (𝑁 ∈ ℕ → (1r‘(ℤ/nℤ‘𝑁)) ∈ (Base‘(ℤ/nℤ‘𝑁)))
3534snssd 4746 . . . 4 (𝑁 ∈ ℕ → {(1r‘(ℤ/nℤ‘𝑁))} ⊆ (Base‘(ℤ/nℤ‘𝑁)))
36 hashcl 14467 . . . . . 6 (𝐷 ∈ Fin → (♯‘𝐷) ∈ ℕ0)
37 nn0cn 12585 . . . . . 6 ((♯‘𝐷) ∈ ℕ0 → (♯‘𝐷) ∈ ℂ)
386, 36, 373syl 19 . . . . 5 (𝑁 ∈ ℕ → (♯‘𝐷) ∈ ℂ)
3938ralrimivw 3158 . . . 4 (𝑁 ∈ ℕ → ∀𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) ∈ ℂ)
403olcd 888 . . . 4 (𝑁 ∈ ℕ → ((Base‘(ℤ/nℤ‘𝑁)) ⊆ (ℤ≥‘0) ∨ (Base‘(ℤ/nℤ‘𝑁)) ∈ Fin))
41 sumss2 15859 . . . 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 851 . . 3 (𝑁 ∈ ℕ → Σ𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) = Σ𝑎 ∈ (Base‘(ℤ/nℤ‘𝑁))if(𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))}, (♯‘𝐷), 0))
434dchrabl 27544 . . . . . 6 (𝑁 ∈ ℕ → 𝐺 ∈ Abel)
44 ablgrp 19960 . . . . . 6 (𝐺 ∈ Abel → 𝐺 ∈ Grp)
455, 21grpidcl 19137 . . . . . 6 (𝐺 ∈ Grp → (0g‘𝐺) ∈ 𝐷)
4643, 44, 453syl 19 . . . . 5 (𝑁 ∈ ℕ → (0g‘𝐺) ∈ 𝐷)
4746snssd 4746 . . . 4 (𝑁 ∈ ℕ → {(0g‘𝐺)} ⊆ 𝐷)
48 phicl 16907 . . . . . 6 (𝑁 ∈ ℕ → (ϕ‘𝑁) ∈ ℕ)
4948nncnd 12320 . . . . 5 (𝑁 ∈ ℕ → (ϕ‘𝑁) ∈ ℂ)
5049ralrimivw 3158 . . . 4 (𝑁 ∈ ℕ → ∀𝑥 ∈ {(0g‘𝐺)} (ϕ‘𝑁) ∈ ℂ)
516olcd 888 . . . 4 (𝑁 ∈ ℕ → (𝐷 ⊆ (ℤ≥‘0) ∨ 𝐷 ∈ Fin))
52 sumss2 15859 . . . 4 ((({(0g‘𝐺)} ⊆ 𝐷 ∧ ∀𝑥 ∈ {(0g‘𝐺)} (ϕ‘𝑁) ∈ ℂ) ∧ (𝐷 ⊆ (ℤ≥‘0) ∨ 𝐷 ∈ Fin)) → Σ𝑥 ∈ {(0g‘𝐺)} (ϕ‘𝑁) = Σ𝑥 ∈ 𝐷 if(𝑥 ∈ {(0g‘𝐺)}, (ϕ‘𝑁), 0))
5347, 50, 51, 52syl21anc 851 . . 3 (𝑁 ∈ ℕ → Σ𝑥 ∈ {(0g‘𝐺)} (ϕ‘𝑁) = Σ𝑥 ∈ 𝐷 if(𝑥 ∈ {(0g‘𝐺)}, (ϕ‘𝑁), 0))
5429, 42, 533eqtr4d 2805 . 2 (𝑁 ∈ ℕ → Σ𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) = Σ𝑥 ∈ {(0g‘𝐺)} (ϕ‘𝑁))
55 eqidd 2761 . . . 4 (𝑎 = (1r‘(ℤ/nℤ‘𝑁)) → (♯‘𝐷) = (♯‘𝐷))
5655sumsn 15879 . . 3 (((1r‘(ℤ/nℤ‘𝑁)) ∈ (Base‘(ℤ/nℤ‘𝑁)) ∧ (♯‘𝐷) ∈ ℂ) → Σ𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) = (♯‘𝐷))
5734, 38, 56syl2anc 596 . 2 (𝑁 ∈ ℕ → Σ𝑎 ∈ {(1r‘(ℤ/nℤ‘𝑁))} (♯‘𝐷) = (♯‘𝐷))
58 eqidd 2761 . . . 4 (𝑥 = (0g‘𝐺) → (ϕ‘𝑁) = (ϕ‘𝑁))
5958sumsn 15879 . . 3 (((0g‘𝐺) ∈ 𝐷 ∧ (ϕ‘𝑁) ∈ ℂ) → Σ𝑥 ∈ {(0g‘𝐺)} (ϕ‘𝑁) = (ϕ‘𝑁))
6046, 49, 59syl2anc 596 . 2 (𝑁 ∈ ℕ → Σ𝑥 ∈ {(0g‘𝐺)} (ϕ‘𝑁) = (ϕ‘𝑁))
6154, 57, 603eqtr3d 2803 1 (𝑁 ∈ ℕ → (♯‘𝐷) = (ϕ‘𝑁))
Colors of variables:    wff setvar class
This proof depends on syntax axioms:   → wi 4   ↔ wb 209   ∧ wa 401   ∨ wo 861   = wceq 1570   ∈ wcel 2145  ∀wral 3076   ⊆ wss 3898  ifcif 4481  {csn 4583  ‘cfv 6527  Fincfn 8951  ℂcc 11169  0cc0 11171  ℕcn 12304  ℕ0cn0 12575  ℤ≥cuz 12934  ♯chash 14441  Σcsu 15820  ϕcphi 16902  Basecbs 17348  0gc0g 17571  Grpcgrp 19105  Abelcabl 19956  1rcur 20368  Ringcrg 20420  CRingccrg 20421  ℤ/nℤczn 21769  DChrcdchr 27522
This proof depends on axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1828  ax-4 1842  ax-5 1943  ax-6 2000  ax-7 2041  ax-8 2147  ax-9 2155  ax-10 2178  ax-11 2194  ax-12 2213  ax-ext 2732  ax-rep 5231  ax-sep 5248  ax-nul 5259  ax-pow 5326  ax-pr 5390  ax-un 7734  ax-inf2 9620  ax-cnex 11227  ax-resscn 11228  ax-1cn 11229  ax-icn 11230  ax-addcl 11231  ax-addrcl 11232  ax-mulcl 11233  ax-mulrcl 11234  ax-mulcom 11235  ax-addass 11236  ax-mulass 11237  ax-distr 11238  ax-i2m1 11239  ax-1ne0 11240  ax-1rid 11241  ax-rnegex 11242  ax-rrecex 11243  ax-cnre 11244  ax-pre-lttri 11245  ax-pre-lttrn 11246  ax-pre-ltadd 11247  ax-pre-mulgt0 11248  ax-pre-sup 11249  ax-addf 11250  ax-mulf 11251
This proof depends on definitions:  df-bi 210  df-an 402  df-or 862  df-3or 1104  df-3an 1105  df-tru 1573  df-fal 1583  df-ex 1813  df-nf 1817  df-sb 2100  df-mo 2564  df-eu 2594  df-clab 2739  df-cleq 2752  df-clel 2835  df-nfc 2909  df-ne 2956  df-nel 3062  df-ral 3077  df-rex 3087  df-rmo 3365  df-reu 3366  df-rab 3413  df-v 3452  df-sbc 3739  df-csb 3847  df-dif 3901  df-un 3903  df-in 3905  df-ss 3915  df-pss 3918  df-nul 4279  df-if 4482  df-pw 4558  df-sn 4584  df-pr 4586  df-tp 4588  df-op 4590  df-uni 4867  df-int 4907  df-iun 4952  df-iin 4953  df-disj 5070  df-br 5103  df-opab 5167  df-mpt 5186  df-tr 5212  df-id 5542  df-eprel 5547  df-po 5555  df-so 5556  df-fr 5600  df-se 5601  df-we 5602  df-xp 5653  df-rel 5654  df-cnv 5655  df-co 5656  df-dm 5657  df-rn 5658  df-res 5659  df-ima 5660  df-pred 6293  df-ord 6354  df-on 6355  df-lim 6356  df-suc 6357  df-iota 6483  df-fun 6529  df-fn 6530  df-f 6531  df-f1 6532  df-fo 6533  df-f1o 6534  df-fv 6535  df-isom 6536  df-riota 7365  df-ov 7411  df-oprab 7412  df-mpo 7413  df-of 7676  df-rpss 7722  df-om 7861  df-1st 7984  df-2nd 7985  df-supp 8156  df-tpos 8221  df-frecs 8277  df-wrecs 8308  df-recs 8357  df-rdg 8396  df-1o 8454  df-2o 8455  df-oadd 8458  df-omul 8459  df-er 8695  df-ec 8697  df-qs 8701  df-map 8827  df-pm 8828  df-ixp 8904  df-en 8952  df-dom 8953  df-sdom 8954  df-fin 8955  df-fsupp 9332  df-fi 9381  df-sup 9412  df-inf 9413  df-oi 9482  df-dju 9953  df-card 9991  df-acn 9994  df-pnf 11316  df-mnf 11317  df-xr 11318  df-ltxr 11319  df-le 11320  df-sub 11514  df-neg 11515  df-div 11943  df-nn 12305  df-2 12374  df-3 12375  df-4 12376  df-5 12377  df-6 12378  df-7 12379  df-8 12380  df-9 12381  df-n0 12576  df-xnn0 12649  df-z 12663  df-dec 12784  df-uz 12935  df-q 13045  df-rp 13090  df-xneg 13210  df-xadd 13211  df-xmul 13212  df-ioo 13449  df-ioc 13450  df-ico 13451  df-icc 13452  df-fz 13609  df-fzo 13757  df-fl 13900  df-mod 13978  df-seq 14113  df-exp 14173  df-fac 14385  df-bc 14414  df-hash 14442  df-word 14626  df-concat 14683  df-s1 14710  df-shft 15187  df-cj 15233  df-re 15234  df-im 15235  df-sqrt 15369  df-abs 15370  df-limsup 15605  df-clim 15622  df-rlim 15623  df-sum 15821  df-ef 16200  df-sin 16202  df-cos 16203  df-pi 16205  df-dvds 16390  df-gcd 16632  df-prm 16809  df-phi 16904  df-pc 16976  df-struct 17286  df-sets 17303  df-slot 17321  df-ndx 17333  df-base 17349  df-ress 17370  df-plusg 17402  df-mulr 17403  df-starv 17404  df-sca 17405  df-vsca 17406  df-ip 17407  df-tset 17408  df-ple 17409  df-ds 17411  df-unif 17412  df-hom 17413  df-cco 17414  df-rest 17554  df-topn 17555  df-0g 17573  df-gsum 17574  df-topgen 17575  df-pt 17576  df-prds 17579  df-xrs 17635  df-qtop 17640  df-imas 17641  df-qus 17642  df-xps 17643  df-mre 17717  df-mrc 17718  df-acs 17720  df-mgm 18777  df-sgrp 18869  df-mnd 18885  df-mhm 18939  df-submnd 18940  df-grp 19108  df-minusg 19109  df-sbg 19110  df-mulg 19239  df-subg 19294  df-nsg 19295  df-eqg 19296  df-ghm 19389  df-gim 19434  df-ga 19465  df-cntz 19492  df-oppg 19521  df-od 19703  df-gex 19704  df-pgp 19705  df-lsm 19811  df-pj1 19812  df-cmn 19957  df-abl 19958  df-cyg 20053  df-dprd 20172  df-dpj 20173  df-mgp 20322  df-rng 20336  df-ur 20369  df-ring 20422  df-cring 20423  df-oppr 20528  df-dvdsr 20548  df-unit 20549  df-invr 20579  df-rhm 20663  df-subrng 20759  df-subrg 20783  df-lmod 21098  df-lss 21168  df-lsp 21208  df-sra 21409  df-rgmod 21410  df-lidl 21447  df-rsp 21448  df-2idl 21504  df-psmet 21631  df-xmet 21632  df-met 21633  df-bl 21634  df-mopn 21635  df-fbas 21636  df-fg 21637  df-cnfld 21640  df-zring 21714  df-zrh 21770  df-zn 21773  df-top 23173  df-topon 23190  df-topsp 23212  df-bases 23225  df-cld 23298  df-ntr 23299  df-cls 23300  df-nei 23377  df-lp 23415  df-perf 23416  df-cn 23506  df-cnp 23507  df-haus 23594  df-tx 23842  df-hmeo 24035  df-fil 24126  df-fm 24218  df-flim 24219  df-flf 24220  df-xms 24600  df-ms 24601  df-tms 24602  df-cncf 25160  df-0p 25952  df-limc 26147  df-dv 26148  df-ply 26467  df-idp 26468  df-coe 26469  df-dgr 26470  df-quot 26575  df-log 26847  df-cxp 26848  df-dchr 27523
This theorem is used by:  sumdchr  27562
  Copyright terms: Public domain W3C validator