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

Theorem znunithash 19894
 Description: The size of the unit group of ℤ/nℤ. (Contributed by Mario Carneiro, 19-Apr-2016.)
Hypotheses
Ref Expression
znchr.y 𝑌 = (ℤ/nℤ‘𝑁)
znunit.u 𝑈 = (Unit‘𝑌)
Assertion
Ref Expression
znunithash (𝑁 ∈ ℕ → (#‘𝑈) = (ϕ‘𝑁))

Proof of Theorem znunithash
Dummy variable 𝑥 is distinct from all other variables.
StepHypRef Expression
1 dfphi2 15460 . 2 (𝑁 ∈ ℕ → (ϕ‘𝑁) = (#‘{𝑥 ∈ (0..^𝑁) ∣ (𝑥 gcd 𝑁) = 1}))
2 nnnn0 11284 . . . . . . . . 9 (𝑁 ∈ ℕ → 𝑁 ∈ ℕ0)
3 znchr.y . . . . . . . . . 10 𝑌 = (ℤ/nℤ‘𝑁)
4 eqid 2620 . . . . . . . . . 10 (Base‘𝑌) = (Base‘𝑌)
5 eqid 2620 . . . . . . . . . 10 ((ℤRHom‘𝑌) ↾ if(𝑁 = 0, ℤ, (0..^𝑁))) = ((ℤRHom‘𝑌) ↾ if(𝑁 = 0, ℤ, (0..^𝑁)))
6 eqid 2620 . . . . . . . . . 10 if(𝑁 = 0, ℤ, (0..^𝑁)) = if(𝑁 = 0, ℤ, (0..^𝑁))
73, 4, 5, 6znf1o 19881 . . . . . . . . 9 (𝑁 ∈ ℕ0 → ((ℤRHom‘𝑌) ↾ if(𝑁 = 0, ℤ, (0..^𝑁))):if(𝑁 = 0, ℤ, (0..^𝑁))–1-1-onto→(Base‘𝑌))
82, 7syl 17 . . . . . . . 8 (𝑁 ∈ ℕ → ((ℤRHom‘𝑌) ↾ if(𝑁 = 0, ℤ, (0..^𝑁))):if(𝑁 = 0, ℤ, (0..^𝑁))–1-1-onto→(Base‘𝑌))
9 nnne0 11038 . . . . . . . . 9 (𝑁 ∈ ℕ → 𝑁 ≠ 0)
10 ifnefalse 4089 . . . . . . . . 9 (𝑁 ≠ 0 → if(𝑁 = 0, ℤ, (0..^𝑁)) = (0..^𝑁))
11 reseq2 5380 . . . . . . . . . . 11 (if(𝑁 = 0, ℤ, (0..^𝑁)) = (0..^𝑁) → ((ℤRHom‘𝑌) ↾ if(𝑁 = 0, ℤ, (0..^𝑁))) = ((ℤRHom‘𝑌) ↾ (0..^𝑁)))
12 f1oeq1 6114 . . . . . . . . . . 11 (((ℤRHom‘𝑌) ↾ if(𝑁 = 0, ℤ, (0..^𝑁))) = ((ℤRHom‘𝑌) ↾ (0..^𝑁)) → (((ℤRHom‘𝑌) ↾ if(𝑁 = 0, ℤ, (0..^𝑁))):if(𝑁 = 0, ℤ, (0..^𝑁))–1-1-onto→(Base‘𝑌) ↔ ((ℤRHom‘𝑌) ↾ (0..^𝑁)):if(𝑁 = 0, ℤ, (0..^𝑁))–1-1-onto→(Base‘𝑌)))
1311, 12syl 17 . . . . . . . . . 10 (if(𝑁 = 0, ℤ, (0..^𝑁)) = (0..^𝑁) → (((ℤRHom‘𝑌) ↾ if(𝑁 = 0, ℤ, (0..^𝑁))):if(𝑁 = 0, ℤ, (0..^𝑁))–1-1-onto→(Base‘𝑌) ↔ ((ℤRHom‘𝑌) ↾ (0..^𝑁)):if(𝑁 = 0, ℤ, (0..^𝑁))–1-1-onto→(Base‘𝑌)))
14 f1oeq2 6115 . . . . . . . . . 10 (if(𝑁 = 0, ℤ, (0..^𝑁)) = (0..^𝑁) → (((ℤRHom‘𝑌) ↾ (0..^𝑁)):if(𝑁 = 0, ℤ, (0..^𝑁))–1-1-onto→(Base‘𝑌) ↔ ((ℤRHom‘𝑌) ↾ (0..^𝑁)):(0..^𝑁)–1-1-onto→(Base‘𝑌)))
1513, 14bitrd 268 . . . . . . . . 9 (if(𝑁 = 0, ℤ, (0..^𝑁)) = (0..^𝑁) → (((ℤRHom‘𝑌) ↾ if(𝑁 = 0, ℤ, (0..^𝑁))):if(𝑁 = 0, ℤ, (0..^𝑁))–1-1-onto→(Base‘𝑌) ↔ ((ℤRHom‘𝑌) ↾ (0..^𝑁)):(0..^𝑁)–1-1-onto→(Base‘𝑌)))
169, 10, 153syl 18 . . . . . . . 8 (𝑁 ∈ ℕ → (((ℤRHom‘𝑌) ↾ if(𝑁 = 0, ℤ, (0..^𝑁))):if(𝑁 = 0, ℤ, (0..^𝑁))–1-1-onto→(Base‘𝑌) ↔ ((ℤRHom‘𝑌) ↾ (0..^𝑁)):(0..^𝑁)–1-1-onto→(Base‘𝑌)))
178, 16mpbid 222 . . . . . . 7 (𝑁 ∈ ℕ → ((ℤRHom‘𝑌) ↾ (0..^𝑁)):(0..^𝑁)–1-1-onto→(Base‘𝑌))
18 f1ofn 6125 . . . . . . 7 (((ℤRHom‘𝑌) ↾ (0..^𝑁)):(0..^𝑁)–1-1-onto→(Base‘𝑌) → ((ℤRHom‘𝑌) ↾ (0..^𝑁)) Fn (0..^𝑁))
19 elpreima 6323 . . . . . . 7 (((ℤRHom‘𝑌) ↾ (0..^𝑁)) Fn (0..^𝑁) → (𝑥 ∈ (((ℤRHom‘𝑌) ↾ (0..^𝑁)) “ 𝑈) ↔ (𝑥 ∈ (0..^𝑁) ∧ (((ℤRHom‘𝑌) ↾ (0..^𝑁))‘𝑥) ∈ 𝑈)))
2017, 18, 193syl 18 . . . . . 6 (𝑁 ∈ ℕ → (𝑥 ∈ (((ℤRHom‘𝑌) ↾ (0..^𝑁)) “ 𝑈) ↔ (𝑥 ∈ (0..^𝑁) ∧ (((ℤRHom‘𝑌) ↾ (0..^𝑁))‘𝑥) ∈ 𝑈)))
21 fvres 6194 . . . . . . . . . 10 (𝑥 ∈ (0..^𝑁) → (((ℤRHom‘𝑌) ↾ (0..^𝑁))‘𝑥) = ((ℤRHom‘𝑌)‘𝑥))
2221adantl 482 . . . . . . . . 9 ((𝑁 ∈ ℕ ∧ 𝑥 ∈ (0..^𝑁)) → (((ℤRHom‘𝑌) ↾ (0..^𝑁))‘𝑥) = ((ℤRHom‘𝑌)‘𝑥))
2322eleq1d 2684 . . . . . . . 8 ((𝑁 ∈ ℕ ∧ 𝑥 ∈ (0..^𝑁)) → ((((ℤRHom‘𝑌) ↾ (0..^𝑁))‘𝑥) ∈ 𝑈 ↔ ((ℤRHom‘𝑌)‘𝑥) ∈ 𝑈))
24 elfzoelz 12454 . . . . . . . . 9 (𝑥 ∈ (0..^𝑁) → 𝑥 ∈ ℤ)
25 znunit.u . . . . . . . . . 10 𝑈 = (Unit‘𝑌)
26 eqid 2620 . . . . . . . . . 10 (ℤRHom‘𝑌) = (ℤRHom‘𝑌)
273, 25, 26znunit 19893 . . . . . . . . 9 ((𝑁 ∈ ℕ0𝑥 ∈ ℤ) → (((ℤRHom‘𝑌)‘𝑥) ∈ 𝑈 ↔ (𝑥 gcd 𝑁) = 1))
282, 24, 27syl2an 494 . . . . . . . 8 ((𝑁 ∈ ℕ ∧ 𝑥 ∈ (0..^𝑁)) → (((ℤRHom‘𝑌)‘𝑥) ∈ 𝑈 ↔ (𝑥 gcd 𝑁) = 1))
2923, 28bitrd 268 . . . . . . 7 ((𝑁 ∈ ℕ ∧ 𝑥 ∈ (0..^𝑁)) → ((((ℤRHom‘𝑌) ↾ (0..^𝑁))‘𝑥) ∈ 𝑈 ↔ (𝑥 gcd 𝑁) = 1))
3029pm5.32da 672 . . . . . 6 (𝑁 ∈ ℕ → ((𝑥 ∈ (0..^𝑁) ∧ (((ℤRHom‘𝑌) ↾ (0..^𝑁))‘𝑥) ∈ 𝑈) ↔ (𝑥 ∈ (0..^𝑁) ∧ (𝑥 gcd 𝑁) = 1)))
3120, 30bitrd 268 . . . . 5 (𝑁 ∈ ℕ → (𝑥 ∈ (((ℤRHom‘𝑌) ↾ (0..^𝑁)) “ 𝑈) ↔ (𝑥 ∈ (0..^𝑁) ∧ (𝑥 gcd 𝑁) = 1)))
3231abbi2dv 2740 . . . 4 (𝑁 ∈ ℕ → (((ℤRHom‘𝑌) ↾ (0..^𝑁)) “ 𝑈) = {𝑥 ∣ (𝑥 ∈ (0..^𝑁) ∧ (𝑥 gcd 𝑁) = 1)})
33 df-rab 2918 . . . 4 {𝑥 ∈ (0..^𝑁) ∣ (𝑥 gcd 𝑁) = 1} = {𝑥 ∣ (𝑥 ∈ (0..^𝑁) ∧ (𝑥 gcd 𝑁) = 1)}
3432, 33syl6eqr 2672 . . 3 (𝑁 ∈ ℕ → (((ℤRHom‘𝑌) ↾ (0..^𝑁)) “ 𝑈) = {𝑥 ∈ (0..^𝑁) ∣ (𝑥 gcd 𝑁) = 1})
3534fveq2d 6182 . 2 (𝑁 ∈ ℕ → (#‘(((ℤRHom‘𝑌) ↾ (0..^𝑁)) “ 𝑈)) = (#‘{𝑥 ∈ (0..^𝑁) ∣ (𝑥 gcd 𝑁) = 1}))
36 f1ocnv 6136 . . . . 5 (((ℤRHom‘𝑌) ↾ (0..^𝑁)):(0..^𝑁)–1-1-onto→(Base‘𝑌) → ((ℤRHom‘𝑌) ↾ (0..^𝑁)):(Base‘𝑌)–1-1-onto→(0..^𝑁))
37 f1of1 6123 . . . . 5 (((ℤRHom‘𝑌) ↾ (0..^𝑁)):(Base‘𝑌)–1-1-onto→(0..^𝑁) → ((ℤRHom‘𝑌) ↾ (0..^𝑁)):(Base‘𝑌)–1-1→(0..^𝑁))
3817, 36, 373syl 18 . . . 4 (𝑁 ∈ ℕ → ((ℤRHom‘𝑌) ↾ (0..^𝑁)):(Base‘𝑌)–1-1→(0..^𝑁))
39 ovexd 6665 . . . 4 (𝑁 ∈ ℕ → (0..^𝑁) ∈ V)
404, 25unitss 18641 . . . . 5 𝑈 ⊆ (Base‘𝑌)
4140a1i 11 . . . 4 (𝑁 ∈ ℕ → 𝑈 ⊆ (Base‘𝑌))
42 fvex 6188 . . . . . 6 (Unit‘𝑌) ∈ V
4325, 42eqeltri 2695 . . . . 5 𝑈 ∈ V
4443a1i 11 . . . 4 (𝑁 ∈ ℕ → 𝑈 ∈ V)
45 f1imaen2g 8002 . . . 4 (((((ℤRHom‘𝑌) ↾ (0..^𝑁)):(Base‘𝑌)–1-1→(0..^𝑁) ∧ (0..^𝑁) ∈ V) ∧ (𝑈 ⊆ (Base‘𝑌) ∧ 𝑈 ∈ V)) → (((ℤRHom‘𝑌) ↾ (0..^𝑁)) “ 𝑈) ≈ 𝑈)
4638, 39, 41, 44, 45syl22anc 1325 . . 3 (𝑁 ∈ ℕ → (((ℤRHom‘𝑌) ↾ (0..^𝑁)) “ 𝑈) ≈ 𝑈)
47 hasheni 13119 . . 3 ((((ℤRHom‘𝑌) ↾ (0..^𝑁)) “ 𝑈) ≈ 𝑈 → (#‘(((ℤRHom‘𝑌) ↾ (0..^𝑁)) “ 𝑈)) = (#‘𝑈))
4846, 47syl 17 . 2 (𝑁 ∈ ℕ → (#‘(((ℤRHom‘𝑌) ↾ (0..^𝑁)) “ 𝑈)) = (#‘𝑈))
491, 35, 483eqtr2rd 2661 1 (𝑁 ∈ ℕ → (#‘𝑈) = (ϕ‘𝑁))
 Colors of variables: wff setvar class Syntax hints:   → wi 4   ↔ wb 196   ∧ wa 384   = wceq 1481   ∈ wcel 1988  {cab 2606   ≠ wne 2791  {crab 2913  Vcvv 3195   ⊆ wss 3567  ifcif 4077   class class class wbr 4644  ◡ccnv 5103   ↾ cres 5106   “ cima 5107   Fn wfn 5871  –1-1→wf1 5873  –1-1-onto→wf1o 5875  ‘cfv 5876  (class class class)co 6635   ≈ cen 7937  0cc0 9921  1c1 9922  ℕcn 11005  ℕ0cn0 11277  ℤcz 11362  ..^cfzo 12449  #chash 13100   gcd cgcd 15197  ϕcphi 15450  Basecbs 15838  Unitcui 18620  ℤRHomczrh 19829  ℤ/nℤczn 19832 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1720  ax-4 1735  ax-5 1837  ax-6 1886  ax-7 1933  ax-8 1990  ax-9 1997  ax-10 2017  ax-11 2032  ax-12 2045  ax-13 2244  ax-ext 2600  ax-rep 4762  ax-sep 4772  ax-nul 4780  ax-pow 4834  ax-pr 4897  ax-un 6934  ax-inf2 8523  ax-cnex 9977  ax-resscn 9978  ax-1cn 9979  ax-icn 9980  ax-addcl 9981  ax-addrcl 9982  ax-mulcl 9983  ax-mulrcl 9984  ax-mulcom 9985  ax-addass 9986  ax-mulass 9987  ax-distr 9988  ax-i2m1 9989  ax-1ne0 9990  ax-1rid 9991  ax-rnegex 9992  ax-rrecex 9993  ax-cnre 9994  ax-pre-lttri 9995  ax-pre-lttrn 9996  ax-pre-ltadd 9997  ax-pre-mulgt0 9998  ax-pre-sup 9999  ax-addf 10000  ax-mulf 10001 This theorem depends on definitions:  df-bi 197  df-or 385  df-an 386  df-3or 1037  df-3an 1038  df-tru 1484  df-ex 1703  df-nf 1708  df-sb 1879  df-eu 2472  df-mo 2473  df-clab 2607  df-cleq 2613  df-clel 2616  df-nfc 2751  df-ne 2792  df-nel 2895  df-ral 2914  df-rex 2915  df-reu 2916  df-rmo 2917  df-rab 2918  df-v 3197  df-sbc 3430  df-csb 3527  df-dif 3570  df-un 3572  df-in 3574  df-ss 3581  df-pss 3583  df-nul 3908  df-if 4078  df-pw 4151  df-sn 4169  df-pr 4171  df-tp 4173  df-op 4175  df-uni 4428  df-int 4467  df-iun 4513  df-br 4645  df-opab 4704  df-mpt 4721  df-tr 4744  df-id 5014  df-eprel 5019  df-po 5025  df-so 5026  df-fr 5063  df-we 5065  df-xp 5110  df-rel 5111  df-cnv 5112  df-co 5113  df-dm 5114  df-rn 5115  df-res 5116  df-ima 5117  df-pred 5668  df-ord 5714  df-on 5715  df-lim 5716  df-suc 5717  df-iota 5839  df-fun 5878  df-fn 5879  df-f 5880  df-f1 5881  df-fo 5882  df-f1o 5883  df-fv 5884  df-riota 6596  df-ov 6638  df-oprab 6639  df-mpt2 6640  df-om 7051  df-1st 7153  df-2nd 7154  df-tpos 7337  df-wrecs 7392  df-recs 7453  df-rdg 7491  df-1o 7545  df-oadd 7549  df-er 7727  df-ec 7729  df-qs 7733  df-map 7844  df-en 7941  df-dom 7942  df-sdom 7943  df-fin 7944  df-sup 8333  df-inf 8334  df-card 8750  df-pnf 10061  df-mnf 10062  df-xr 10063  df-ltxr 10064  df-le 10065  df-sub 10253  df-neg 10254  df-div 10670  df-nn 11006  df-2 11064  df-3 11065  df-4 11066  df-5 11067  df-6 11068  df-7 11069  df-8 11070  df-9 11071  df-n0 11278  df-xnn0 11349  df-z 11363  df-dec 11479  df-uz 11673  df-rp 11818  df-fz 12312  df-fzo 12450  df-fl 12576  df-mod 12652  df-seq 12785  df-exp 12844  df-hash 13101  df-cj 13820  df-re 13821  df-im 13822  df-sqrt 13956  df-abs 13957  df-dvds 14965  df-gcd 15198  df-phi 15452  df-struct 15840  df-ndx 15841  df-slot 15842  df-base 15844  df-sets 15845  df-ress 15846  df-plusg 15935  df-mulr 15936  df-starv 15937  df-sca 15938  df-vsca 15939  df-ip 15940  df-tset 15941  df-ple 15942  df-ds 15945  df-unif 15946  df-0g 16083  df-imas 16149  df-qus 16150  df-mgm 17223  df-sgrp 17265  df-mnd 17276  df-mhm 17316  df-grp 17406  df-minusg 17407  df-sbg 17408  df-mulg 17522  df-subg 17572  df-nsg 17573  df-eqg 17574  df-ghm 17639  df-cmn 18176  df-abl 18177  df-mgp 18471  df-ur 18483  df-ring 18530  df-cring 18531  df-oppr 18604  df-dvdsr 18622  df-unit 18623  df-rnghom 18696  df-subrg 18759  df-lmod 18846  df-lss 18914  df-lsp 18953  df-sra 19153  df-rgmod 19154  df-lidl 19155  df-rsp 19156  df-2idl 19213  df-cnfld 19728  df-zring 19800  df-zrh 19833  df-zn 19836 This theorem is referenced by:  dchrfi  24961  dchrsum2  24974
 Copyright terms: Public domain W3C validator