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

Theorem dchrhash 24176
Description: There are exactly  phi ( N ) Dirichlet characters modulo  N. Part of Theorem 6.5.1 of [Shapiro] p. 230. (Contributed by Mario Carneiro, 28-Apr-2016.)
Hypotheses
Ref Expression
sumdchr.g  |-  G  =  (DChr `  N )
sumdchr.d  |-  D  =  ( Base `  G
)
Assertion
Ref Expression
dchrhash  |-  ( N  e.  NN  ->  ( # `
 D )  =  ( phi `  N
) )

Proof of Theorem dchrhash
Dummy variables  x  a are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 eqid 2420 . . . . . 6  |-  (ℤ/n `  N
)  =  (ℤ/n `  N
)
2 eqid 2420 . . . . . 6  |-  ( Base `  (ℤ/n `  N ) )  =  ( Base `  (ℤ/n `  N
) )
31, 2znfi 19107 . . . . 5  |-  ( N  e.  NN  ->  ( Base `  (ℤ/n `  N ) )  e. 
Fin )
4 sumdchr.g . . . . . 6  |-  G  =  (DChr `  N )
5 sumdchr.d . . . . . 6  |-  D  =  ( Base `  G
)
64, 5dchrfi 24160 . . . . 5  |-  ( N  e.  NN  ->  D  e.  Fin )
7 simprr 764 . . . . . . 7  |-  ( ( N  e.  NN  /\  ( a  e.  (
Base `  (ℤ/n `  N ) )  /\  x  e.  D )
)  ->  x  e.  D )
84, 1, 5, 2, 7dchrf 24147 . . . . . 6  |-  ( ( N  e.  NN  /\  ( a  e.  (
Base `  (ℤ/n `  N ) )  /\  x  e.  D )
)  ->  x :
( Base `  (ℤ/n `  N ) ) --> CC )
9 simprl 762 . . . . . 6  |-  ( ( N  e.  NN  /\  ( a  e.  (
Base `  (ℤ/n `  N ) )  /\  x  e.  D )
)  ->  a  e.  ( Base `  (ℤ/n `  N ) ) )
108, 9ffvelrnd 6030 . . . . 5  |-  ( ( N  e.  NN  /\  ( a  e.  (
Base `  (ℤ/n `  N ) )  /\  x  e.  D )
)  ->  ( x `  a )  e.  CC )
113, 6, 10fsumcom 13814 . . . 4  |-  ( N  e.  NN  ->  sum_ a  e.  ( Base `  (ℤ/n `  N
) ) sum_ x  e.  D  ( x `  a )  =  sum_ x  e.  D  sum_ a  e.  ( Base `  (ℤ/n `  N
) ) ( x `
 a ) )
12 eqid 2420 . . . . . . 7  |-  ( 1r
`  (ℤ/n `  N ) )  =  ( 1r `  (ℤ/n `  N
) )
13 simpl 458 . . . . . . 7  |-  ( ( N  e.  NN  /\  a  e.  ( Base `  (ℤ/n `  N ) ) )  ->  N  e.  NN )
14 simpr 462 . . . . . . 7  |-  ( ( N  e.  NN  /\  a  e.  ( Base `  (ℤ/n `  N ) ) )  ->  a  e.  (
Base `  (ℤ/n `  N ) ) )
154, 5, 1, 12, 2, 13, 14sumdchr2 24175 . . . . . 6  |-  ( ( N  e.  NN  /\  a  e.  ( Base `  (ℤ/n `  N ) ) )  ->  sum_ x  e.  D  ( x `  a
)  =  if ( a  =  ( 1r
`  (ℤ/n `  N ) ) ,  ( # `  D
) ,  0 ) )
16 elsn 4007 . . . . . . 7  |-  ( a  e.  { ( 1r
`  (ℤ/n `  N ) ) }  <-> 
a  =  ( 1r
`  (ℤ/n `  N ) ) )
17 ifbi 3927 . . . . . . 7  |-  ( ( a  e.  { ( 1r `  (ℤ/n `  N
) ) }  <->  a  =  ( 1r `  (ℤ/n `  N
) ) )  ->  if ( a  e.  {
( 1r `  (ℤ/n `  N
) ) } , 
( # `  D ) ,  0 )  =  if ( a  =  ( 1r `  (ℤ/n `  N
) ) ,  (
# `  D ) ,  0 ) )
1816, 17mp1i 13 . . . . . 6  |-  ( ( N  e.  NN  /\  a  e.  ( Base `  (ℤ/n `  N ) ) )  ->  if ( a  e.  { ( 1r
`  (ℤ/n `  N ) ) } ,  ( # `  D
) ,  0 )  =  if ( a  =  ( 1r `  (ℤ/n `  N ) ) ,  ( # `  D
) ,  0 ) )
1915, 18eqtr4d 2464 . . . . 5  |-  ( ( N  e.  NN  /\  a  e.  ( Base `  (ℤ/n `  N ) ) )  ->  sum_ x  e.  D  ( x `  a
)  =  if ( a  e.  { ( 1r `  (ℤ/n `  N
) ) } , 
( # `  D ) ,  0 ) )
2019sumeq2dv 13747 . . . 4  |-  ( N  e.  NN  ->  sum_ a  e.  ( Base `  (ℤ/n `  N
) ) sum_ x  e.  D  ( x `  a )  =  sum_ a  e.  ( Base `  (ℤ/n `  N ) ) if ( a  e.  {
( 1r `  (ℤ/n `  N
) ) } , 
( # `  D ) ,  0 ) )
21 eqid 2420 . . . . . . 7  |-  ( 0g
`  G )  =  ( 0g `  G
)
22 simpr 462 . . . . . . 7  |-  ( ( N  e.  NN  /\  x  e.  D )  ->  x  e.  D )
234, 1, 5, 21, 22, 2dchrsum 24174 . . . . . 6  |-  ( ( N  e.  NN  /\  x  e.  D )  -> 
sum_ a  e.  (
Base `  (ℤ/n `  N ) ) ( x `  a )  =  if ( x  =  ( 0g `  G ) ,  ( phi `  N ) ,  0 ) )
24 elsn 4007 . . . . . . 7  |-  ( x  e.  { ( 0g
`  G ) }  <-> 
x  =  ( 0g
`  G ) )
25 ifbi 3927 . . . . . . 7  |-  ( ( x  e.  { ( 0g `  G ) }  <->  x  =  ( 0g `  G ) )  ->  if ( x  e.  { ( 0g
`  G ) } ,  ( phi `  N ) ,  0 )  =  if ( x  =  ( 0g
`  G ) ,  ( phi `  N
) ,  0 ) )
2624, 25mp1i 13 . . . . . 6  |-  ( ( N  e.  NN  /\  x  e.  D )  ->  if ( x  e. 
{ ( 0g `  G ) } , 
( phi `  N
) ,  0 )  =  if ( x  =  ( 0g `  G ) ,  ( phi `  N ) ,  0 ) )
2723, 26eqtr4d 2464 . . . . 5  |-  ( ( N  e.  NN  /\  x  e.  D )  -> 
sum_ a  e.  (
Base `  (ℤ/n `  N ) ) ( x `  a )  =  if ( x  e.  { ( 0g
`  G ) } ,  ( phi `  N ) ,  0 ) )
2827sumeq2dv 13747 . . . 4  |-  ( N  e.  NN  ->  sum_ x  e.  D  sum_ a  e.  ( Base `  (ℤ/n `  N
) ) ( x `
 a )  = 
sum_ x  e.  D  if ( x  e.  {
( 0g `  G
) } ,  ( phi `  N ) ,  0 ) )
2911, 20, 283eqtr3d 2469 . . 3  |-  ( N  e.  NN  ->  sum_ a  e.  ( Base `  (ℤ/n `  N
) ) if ( a  e.  { ( 1r `  (ℤ/n `  N
) ) } , 
( # `  D ) ,  0 )  = 
sum_ x  e.  D  if ( x  e.  {
( 0g `  G
) } ,  ( phi `  N ) ,  0 ) )
30 nnnn0 10872 . . . . . 6  |-  ( N  e.  NN  ->  N  e.  NN0 )
311zncrng 19092 . . . . . 6  |-  ( N  e.  NN0  ->  (ℤ/n `  N
)  e.  CRing )
32 crngring 17769 . . . . . 6  |-  ( (ℤ/n `  N )  e.  CRing  -> 
(ℤ/n `  N )  e.  Ring )
332, 12ringidcl 17779 . . . . . 6  |-  ( (ℤ/n `  N )  e.  Ring  -> 
( 1r `  (ℤ/n `  N
) )  e.  (
Base `  (ℤ/n `  N ) ) )
3430, 31, 32, 334syl 19 . . . . 5  |-  ( N  e.  NN  ->  ( 1r `  (ℤ/n `  N ) )  e.  ( Base `  (ℤ/n `  N
) ) )
3534snssd 4139 . . . 4  |-  ( N  e.  NN  ->  { ( 1r `  (ℤ/n `  N
) ) }  C_  ( Base `  (ℤ/n `  N ) ) )
36 hashcl 12531 . . . . . 6  |-  ( D  e.  Fin  ->  ( # `
 D )  e. 
NN0 )
37 nn0cn 10875 . . . . . 6  |-  ( (
# `  D )  e.  NN0  ->  ( # `  D
)  e.  CC )
386, 36, 373syl 18 . . . . 5  |-  ( N  e.  NN  ->  ( # `
 D )  e.  CC )
3938ralrimivw 2838 . . . 4  |-  ( N  e.  NN  ->  A. a  e.  { ( 1r `  (ℤ/n `  N ) ) }  ( # `  D
)  e.  CC )
403olcd 394 . . . 4  |-  ( N  e.  NN  ->  (
( Base `  (ℤ/n `  N ) )  C_  ( ZZ>= `  0 )  \/  ( Base `  (ℤ/n `  N
) )  e.  Fin ) )
41 sumss2 13770 . . . 4  |-  ( ( ( { ( 1r
`  (ℤ/n `  N ) ) } 
C_  ( Base `  (ℤ/n `  N
) )  /\  A. a  e.  { ( 1r `  (ℤ/n `  N ) ) }  ( # `  D
)  e.  CC )  /\  ( ( Base `  (ℤ/n `  N ) )  C_  ( ZZ>= `  0 )  \/  ( Base `  (ℤ/n `  N
) )  e.  Fin ) )  ->  sum_ a  e.  { ( 1r `  (ℤ/n `  N ) ) }  ( # `  D
)  =  sum_ a  e.  ( Base `  (ℤ/n `  N
) ) if ( a  e.  { ( 1r `  (ℤ/n `  N
) ) } , 
( # `  D ) ,  0 ) )
4235, 39, 40, 41syl21anc 1263 . . 3  |-  ( N  e.  NN  ->  sum_ a  e.  { ( 1r `  (ℤ/n `  N ) ) }  ( # `  D
)  =  sum_ a  e.  ( Base `  (ℤ/n `  N
) ) if ( a  e.  { ( 1r `  (ℤ/n `  N
) ) } , 
( # `  D ) ,  0 ) )
434dchrabl 24159 . . . . . 6  |-  ( N  e.  NN  ->  G  e.  Abel )
44 ablgrp 17413 . . . . . 6  |-  ( G  e.  Abel  ->  G  e. 
Grp )
455, 21grpidcl 16672 . . . . . 6  |-  ( G  e.  Grp  ->  ( 0g `  G )  e.  D )
4643, 44, 453syl 18 . . . . 5  |-  ( N  e.  NN  ->  ( 0g `  G )  e.  D )
4746snssd 4139 . . . 4  |-  ( N  e.  NN  ->  { ( 0g `  G ) }  C_  D )
48 phicl 14695 . . . . . 6  |-  ( N  e.  NN  ->  ( phi `  N )  e.  NN )
4948nncnd 10621 . . . . 5  |-  ( N  e.  NN  ->  ( phi `  N )  e.  CC )
5049ralrimivw 2838 . . . 4  |-  ( N  e.  NN  ->  A. x  e.  { ( 0g `  G ) }  ( phi `  N )  e.  CC )
516olcd 394 . . . 4  |-  ( N  e.  NN  ->  ( D  C_  ( ZZ>= `  0
)  \/  D  e. 
Fin ) )
52 sumss2 13770 . . . 4  |-  ( ( ( { ( 0g
`  G ) } 
C_  D  /\  A. x  e.  { ( 0g `  G ) }  ( phi `  N
)  e.  CC )  /\  ( D  C_  ( ZZ>= `  0 )  \/  D  e.  Fin ) )  ->  sum_ x  e.  { ( 0g `  G ) }  ( phi `  N )  = 
sum_ x  e.  D  if ( x  e.  {
( 0g `  G
) } ,  ( phi `  N ) ,  0 ) )
5347, 50, 51, 52syl21anc 1263 . . 3  |-  ( N  e.  NN  ->  sum_ x  e.  { ( 0g `  G ) }  ( phi `  N )  = 
sum_ x  e.  D  if ( x  e.  {
( 0g `  G
) } ,  ( phi `  N ) ,  0 ) )
5429, 42, 533eqtr4d 2471 . 2  |-  ( N  e.  NN  ->  sum_ a  e.  { ( 1r `  (ℤ/n `  N ) ) }  ( # `  D
)  =  sum_ x  e.  { ( 0g `  G ) }  ( phi `  N ) )
55 eqidd 2421 . . . 4  |-  ( a  =  ( 1r `  (ℤ/n `  N ) )  -> 
( # `  D )  =  ( # `  D
) )
5655sumsn 13785 . . 3  |-  ( ( ( 1r `  (ℤ/n `  N
) )  e.  (
Base `  (ℤ/n `  N ) )  /\  ( # `  D )  e.  CC )  ->  sum_ a  e.  { ( 1r `  (ℤ/n `  N
) ) }  ( # `
 D )  =  ( # `  D
) )
5734, 38, 56syl2anc 665 . 2  |-  ( N  e.  NN  ->  sum_ a  e.  { ( 1r `  (ℤ/n `  N ) ) }  ( # `  D
)  =  ( # `  D ) )
58 eqidd 2421 . . . 4  |-  ( x  =  ( 0g `  G )  ->  ( phi `  N )  =  ( phi `  N
) )
5958sumsn 13785 . . 3  |-  ( ( ( 0g `  G
)  e.  D  /\  ( phi `  N )  e.  CC )  ->  sum_ x  e.  { ( 0g `  G ) }  ( phi `  N )  =  ( phi `  N ) )
6046, 49, 59syl2anc 665 . 2  |-  ( N  e.  NN  ->  sum_ x  e.  { ( 0g `  G ) }  ( phi `  N )  =  ( phi `  N
) )
6154, 57, 603eqtr3d 2469 1  |-  ( N  e.  NN  ->  ( # `
 D )  =  ( phi `  N
) )
Colors of variables: wff setvar class
Syntax hints:    -> wi 4    <-> wb 187    \/ wo 369    /\ wa 370    = wceq 1437    e. wcel 1867   A.wral 2773    C_ wss 3433   ifcif 3906   {csn 3993   ` cfv 5593   Fincfn 7569   CCcc 9533   0cc0 9535   NNcn 10605   NN0cn0 10865   ZZ>=cuz 11155   #chash 12508   sum_csu 13730   phicphi 14689   Basecbs 15099   0gc0g 15316   Grpcgrp 16647   Abelcabl 17409   1rcur 17713   Ringcrg 17758   CRingccrg 17759  ℤ/nczn 19051  DChrcdchr 24137
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1665  ax-4 1678  ax-5 1748  ax-6 1794  ax-7 1838  ax-8 1869  ax-9 1871  ax-10 1886  ax-11 1891  ax-12 1904  ax-13 2052  ax-ext 2398  ax-rep 4530  ax-sep 4540  ax-nul 4548  ax-pow 4595  ax-pr 4653  ax-un 6589  ax-inf2 8144  ax-cnex 9591  ax-resscn 9592  ax-1cn 9593  ax-icn 9594  ax-addcl 9595  ax-addrcl 9596  ax-mulcl 9597  ax-mulrcl 9598  ax-mulcom 9599  ax-addass 9600  ax-mulass 9601  ax-distr 9602  ax-i2m1 9603  ax-1ne0 9604  ax-1rid 9605  ax-rnegex 9606  ax-rrecex 9607  ax-cnre 9608  ax-pre-lttri 9609  ax-pre-lttrn 9610  ax-pre-ltadd 9611  ax-pre-mulgt0 9612  ax-pre-sup 9613  ax-addf 9614  ax-mulf 9615
This theorem depends on definitions:  df-bi 188  df-or 371  df-an 372  df-3or 983  df-3an 984  df-tru 1440  df-fal 1443  df-ex 1660  df-nf 1664  df-sb 1787  df-eu 2267  df-mo 2268  df-clab 2406  df-cleq 2412  df-clel 2415  df-nfc 2570  df-ne 2618  df-nel 2619  df-ral 2778  df-rex 2779  df-reu 2780  df-rmo 2781  df-rab 2782  df-v 3080  df-sbc 3297  df-csb 3393  df-dif 3436  df-un 3438  df-in 3440  df-ss 3447  df-pss 3449  df-nul 3759  df-if 3907  df-pw 3978  df-sn 3994  df-pr 3996  df-tp 3998  df-op 4000  df-uni 4214  df-int 4250  df-iun 4295  df-iin 4296  df-disj 4389  df-br 4418  df-opab 4477  df-mpt 4478  df-tr 4513  df-eprel 4757  df-id 4761  df-po 4767  df-so 4768  df-fr 4805  df-se 4806  df-we 4807  df-xp 4852  df-rel 4853  df-cnv 4854  df-co 4855  df-dm 4856  df-rn 4857  df-res 4858  df-ima 4859  df-pred 5391  df-ord 5437  df-on 5438  df-lim 5439  df-suc 5440  df-iota 5557  df-fun 5595  df-fn 5596  df-f 5597  df-f1 5598  df-fo 5599  df-f1o 5600  df-fv 5601  df-isom 5602  df-riota 6259  df-ov 6300  df-oprab 6301  df-mpt2 6302  df-of 6537  df-rpss 6577  df-om 6699  df-1st 6799  df-2nd 6800  df-supp 6918  df-tpos 6973  df-wrecs 7028  df-recs 7090  df-rdg 7128  df-1o 7182  df-2o 7183  df-oadd 7186  df-omul 7187  df-er 7363  df-ec 7365  df-qs 7369  df-map 7474  df-pm 7475  df-ixp 7523  df-en 7570  df-dom 7571  df-sdom 7572  df-fin 7573  df-fsupp 7882  df-fi 7923  df-sup 7954  df-inf 7955  df-oi 8023  df-card 8370  df-acn 8373  df-cda 8594  df-pnf 9673  df-mnf 9674  df-xr 9675  df-ltxr 9676  df-le 9677  df-sub 9858  df-neg 9859  df-div 10266  df-nn 10606  df-2 10664  df-3 10665  df-4 10666  df-5 10667  df-6 10668  df-7 10669  df-8 10670  df-9 10671  df-10 10672  df-n0 10866  df-z 10934  df-dec 11048  df-uz 11156  df-q 11261  df-rp 11299  df-xneg 11405  df-xadd 11406  df-xmul 11407  df-ioo 11635  df-ioc 11636  df-ico 11637  df-icc 11638  df-fz 11779  df-fzo 11910  df-fl 12021  df-mod 12090  df-seq 12207  df-exp 12266  df-fac 12453  df-bc 12481  df-hash 12509  df-word 12647  df-concat 12649  df-s1 12650  df-shft 13109  df-cj 13141  df-re 13142  df-im 13143  df-sqrt 13277  df-abs 13278  df-limsup 13504  df-clim 13530  df-rlim 13531  df-sum 13731  df-ef 14099  df-sin 14101  df-cos 14102  df-pi 14104  df-dvds 14284  df-gcd 14447  df-prm 14601  df-phi 14692  df-pc 14765  df-struct 15101  df-ndx 15102  df-slot 15103  df-base 15104  df-sets 15105  df-ress 15106  df-plusg 15181  df-mulr 15182  df-starv 15183  df-sca 15184  df-vsca 15185  df-ip 15186  df-tset 15187  df-ple 15188  df-ds 15190  df-unif 15191  df-hom 15192  df-cco 15193  df-rest 15299  df-topn 15300  df-0g 15318  df-gsum 15319  df-topgen 15320  df-pt 15321  df-prds 15324  df-xrs 15378  df-qtop 15384  df-imas 15385  df-qus 15387  df-xps 15388  df-mre 15470  df-mrc 15471  df-acs 15473  df-mgm 16466  df-sgrp 16505  df-mnd 16515  df-mhm 16560  df-submnd 16561  df-grp 16651  df-minusg 16652  df-sbg 16653  df-mulg 16654  df-subg 16792  df-nsg 16793  df-eqg 16794  df-ghm 16859  df-gim 16901  df-ga 16922  df-cntz 16949  df-oppg 16975  df-od 17150  df-gex 17152  df-pgp 17154  df-lsm 17266  df-pj1 17267  df-cmn 17410  df-abl 17411  df-cyg 17491  df-dprd 17605  df-dpj 17606  df-mgp 17702  df-ur 17714  df-ring 17760  df-cring 17761  df-oppr 17829  df-dvdsr 17847  df-unit 17848  df-invr 17878  df-rnghom 17921  df-subrg 17984  df-lmod 18071  df-lss 18134  df-lsp 18173  df-sra 18373  df-rgmod 18374  df-lidl 18375  df-rsp 18376  df-2idl 18434  df-psmet 18940  df-xmet 18941  df-met 18942  df-bl 18943  df-mopn 18944  df-fbas 18945  df-fg 18946  df-cnfld 18949  df-zring 19017  df-zrh 19052  df-zn 19055  df-top 19898  df-bases 19899  df-topon 19900  df-topsp 19901  df-cld 20011  df-ntr 20012  df-cls 20013  df-nei 20091  df-lp 20129  df-perf 20130  df-cn 20220  df-cnp 20221  df-haus 20308  df-tx 20554  df-hmeo 20747  df-fil 20838  df-fm 20930  df-flim 20931  df-flf 20932  df-xms 21312  df-ms 21313  df-tms 21314  df-cncf 21887  df-0p 22605  df-limc 22798  df-dv 22799  df-ply 23119  df-idp 23120  df-coe 23121  df-dgr 23122  df-quot 23221  df-log 23483  df-cxp 23484  df-dchr 24138
This theorem is referenced by:  sumdchr  24177
  Copyright terms: Public domain W3C validator