Theorem dfphi2 11735

Description: Alternate definition of the Euler phi function. (Contributed by Mario Carneiro, 23-Feb-2014.) (Revised by Mario Carneiro, 2-May-2016.)

Assertion

Ref	Expression
dfphi2	|- ( N e. NN -> ( phi ` N ) = (♯ ` { x e. ( 0..^ N ) | ( x gcd N ) = 1 } ) )

Distinct variable group:   x, N

Proof of Theorem dfphi2

Step	Hyp	Ref	Expression
1		elnn1uz2 9297	. 2 |- ( N e. NN <-> ( N = 1 \/ N e. ( ZZ>= ` 2 ) ) )
2		phi1 11734	. . . . 5 |- ( phi ` 1 ) = 1
3		0z 8963	. . . . . 6 |- 0 e. ZZ
4		hashsng 10431	. . . . . 6 |- ( 0 e. ZZ -> (♯ ` { 0 } ) = 1 )
5	3, 4	ax-mp 7	. . . . 5 |- (♯ ` { 0 } ) = 1
6		rabid2 2579	. . . . . . 7 |- ( { 0 } = { x e. { 0 } | ( x gcd 1 ) = 1 } <-> A. x e. { 0 } ( x gcd 1 ) = 1 )
7		elsni 3509	. . . . . . . . 9 |- ( x e. { 0 } -> x = 0 )
8	7	oveq1d 5741	. . . . . . . 8 |- ( x e. { 0 } -> ( x gcd 1 ) = ( 0 gcd 1 ) )
9		gcd1 11517	. . . . . . . . 9 |- ( 0 e. ZZ -> ( 0 gcd 1 ) = 1 )
10	3, 9	ax-mp 7	. . . . . . . 8 |- ( 0 gcd 1 ) = 1
11	8, 10	syl6eq 2161	. . . . . . 7 |- ( x e. { 0 } -> ( x gcd 1 ) = 1 )
12	6, 11	mprgbir 2462	. . . . . 6 |- { 0 } = { x e. { 0 } | ( x gcd 1 ) = 1 }
13	12	fveq2i 5376	. . . . 5 |- (♯ ` { 0 } ) = (♯ ` { x e. { 0 } | ( x gcd 1 ) = 1 } )
14	2, 5, 13	3eqtr2i 2139	. . . 4 |- ( phi ` 1 ) = (♯ ` { x e. { 0 } | ( x gcd 1 ) = 1 } )
15		fveq2 5373	. . . 4 |- ( N = 1 -> ( phi ` N ) = ( phi ` 1 ) )
16		oveq2 5734	. . . . . . 7 |- ( N = 1 -> ( 0..^ N ) = ( 0..^ 1 ) )
17		fzo01 9880	. . . . . . 7 |- ( 0..^ 1 ) = { 0 }
18	16, 17	syl6eq 2161	. . . . . 6 |- ( N = 1 -> ( 0..^ N ) = { 0 } )
19		oveq2 5734	. . . . . . 7 |- ( N = 1 -> ( x gcd N ) = ( x gcd 1 ) )
20	19	eqeq1d 2121	. . . . . 6 |- ( N = 1 -> ( ( x gcd N ) = 1 <-> ( x gcd 1 ) = 1 ) )
21	18, 20	rabeqbidv 2650	. . . . 5 |- ( N = 1 -> { x e. ( 0..^ N ) | ( x gcd N ) = 1 } = { x e. { 0 } | ( x gcd 1 ) = 1 } )
22	21	fveq2d 5377	. . . 4 |- ( N = 1 -> (♯ ` { x e. ( 0..^ N ) | ( x gcd N ) = 1 } ) = (♯ ` { x e. { 0 } | ( x gcd 1 ) = 1 } ) )
23	14, 15, 22	3eqtr4a 2171	. . 3 |- ( N = 1 -> ( phi ` N ) = (♯ ` { x e. ( 0..^ N ) | ( x gcd N ) = 1 } ) )
24		eluz2nn 9260	. . . . 5 |- ( N e. ( ZZ>= ` 2 ) -> N e. NN )
25		phival 11728	. . . . 5 |- ( N e. NN -> ( phi ` N ) = (♯ ` { x e. ( 1 ... N ) | ( x gcd N ) = 1 } ) )
26	24, 25	syl 14	. . . 4 |- ( N e. ( ZZ>= ` 2 ) -> ( phi ` N ) = (♯ ` { x e. ( 1 ... N ) | ( x gcd N ) = 1 } ) )
27		fzossfz 9829	. . . . . . . . . . 11 |- ( 1..^ N ) C_ ( 1 ... N )
28	27	a1i 9	. . . . . . . . . 10 |- ( N e. ( ZZ>= ` 2 ) -> ( 1..^ N ) C_ ( 1 ... N ) )
29		sseqin2 3259	. . . . . . . . . 10 |- ( ( 1..^ N ) C_ ( 1 ... N ) <-> ( ( 1 ... N ) i^i ( 1..^ N ) ) = ( 1..^ N ) )
30	28, 29	sylib 121	. . . . . . . . 9 |- ( N e. ( ZZ>= ` 2 ) -> ( ( 1 ... N ) i^i ( 1..^ N ) ) = ( 1..^ N ) )
31		fzo0ss1 9838	. . . . . . . . . 10 |- ( 1..^ N ) C_ ( 0..^ N )
32		sseqin2 3259	. . . . . . . . . 10 |- ( ( 1..^ N ) C_ ( 0..^ N ) <-> ( ( 0..^ N ) i^i ( 1..^ N ) ) = ( 1..^ N ) )
33	31, 32	mpbi 144	. . . . . . . . 9 |- ( ( 0..^ N ) i^i ( 1..^ N ) ) = ( 1..^ N )
34	30, 33	syl6eqr 2163	. . . . . . . 8 |- ( N e. ( ZZ>= ` 2 ) -> ( ( 1 ... N ) i^i ( 1..^ N ) ) = ( ( 0..^ N ) i^i ( 1..^ N ) ) )
35	34	rabeqdv 2649	. . . . . . 7 |- ( N e. ( ZZ>= ` 2 ) -> { x e. ( ( 1 ... N ) i^i ( 1..^ N ) ) | ( x gcd N ) = 1 } = { x e. ( ( 0..^ N ) i^i ( 1..^ N ) ) | ( x gcd N ) = 1 } )
36		inrab2 3313	. . . . . . 7 |- ( { x e. ( 1 ... N ) | ( x gcd N ) = 1 } i^i ( 1..^ N ) ) = { x e. ( ( 1 ... N ) i^i ( 1..^ N ) ) | ( x gcd N ) = 1 }
37		inrab2 3313	. . . . . . 7 |- ( { x e. ( 0..^ N ) | ( x gcd N ) = 1 } i^i ( 1..^ N ) ) = { x e. ( ( 0..^ N ) i^i ( 1..^ N ) ) | ( x gcd N ) = 1 }
38	35, 36, 37	3eqtr4g 2170	. . . . . 6 |- ( N e. ( ZZ>= ` 2 ) -> ( { x e. ( 1 ... N ) | ( x gcd N ) = 1 } i^i ( 1..^ N ) ) = ( { x e. ( 0..^ N ) | ( x gcd N ) = 1 } i^i ( 1..^ N ) ) )
39		phibndlem 11731	. . . . . . . 8 |- ( N e. ( ZZ>= ` 2 ) -> { x e. ( 1 ... N ) | ( x gcd N ) = 1 } C_ ( 1 ... ( N - 1 ) ) )
40		eluzelz 9231	. . . . . . . . 9 |- ( N e. ( ZZ>= ` 2 ) -> N e. ZZ )
41		fzoval 9812	. . . . . . . . 9 |- ( N e. ZZ -> ( 1..^ N ) = ( 1 ... ( N - 1 ) ) )
42	40, 41	syl 14	. . . . . . . 8 |- ( N e. ( ZZ>= ` 2 ) -> ( 1..^ N ) = ( 1 ... ( N - 1 ) ) )
43	39, 42	sseqtr4d 3100	. . . . . . 7 |- ( N e. ( ZZ>= ` 2 ) -> { x e. ( 1 ... N ) | ( x gcd N ) = 1 } C_ ( 1..^ N ) )
44		df-ss 3048	. . . . . . 7 |- ( { x e. ( 1 ... N ) | ( x gcd N ) = 1 } C_ ( 1..^ N ) <-> ( { x e. ( 1 ... N ) | ( x gcd N ) = 1 } i^i ( 1..^ N ) ) = { x e. ( 1 ... N ) | ( x gcd N ) = 1 } )
45	43, 44	sylib 121	. . . . . 6 |- ( N e. ( ZZ>= ` 2 ) -> ( { x e. ( 1 ... N ) | ( x gcd N ) = 1 } i^i ( 1..^ N ) ) = { x e. ( 1 ... N ) | ( x gcd N ) = 1 } )
46		gcd0id 11509	. . . . . . . . . . . . . . . 16 |- ( N e. ZZ -> ( 0 gcd N ) = ( abs ` N ) )
47	40, 46	syl 14	. . . . . . . . . . . . . . 15 |- ( N e. ( ZZ>= ` 2 ) -> ( 0 gcd N ) = ( abs ` N ) )
48		eluzelre 9232	. . . . . . . . . . . . . . . 16 |- ( N e. ( ZZ>= ` 2 ) -> N e. RR )
49		eluzge2nn0 9261	. . . . . . . . . . . . . . . . 17 |- ( N e. ( ZZ>= ` 2 ) -> N e. NN0 )
50	49	nn0ge0d 8931	. . . . . . . . . . . . . . . 16 |- ( N e. ( ZZ>= ` 2 ) -> 0 <_ N )
51	48, 50	absidd 10825	. . . . . . . . . . . . . . 15 |- ( N e. ( ZZ>= ` 2 ) -> ( abs ` N ) = N )
52	47, 51	eqtrd 2145	. . . . . . . . . . . . . 14 |- ( N e. ( ZZ>= ` 2 ) -> ( 0 gcd N ) = N )
53		eluz2b3 9294	. . . . . . . . . . . . . . 15 |- ( N e. ( ZZ>= ` 2 ) <-> ( N e. NN /\ N =/= 1 ) )
54	53	simprbi 271	. . . . . . . . . . . . . 14 |- ( N e. ( ZZ>= ` 2 ) -> N =/= 1 )
55	52, 54	eqnetrd 2304	. . . . . . . . . . . . 13 |- ( N e. ( ZZ>= ` 2 ) -> ( 0 gcd N ) =/= 1 )
56	55	adantr 272	. . . . . . . . . . . 12 |- ( ( N e. ( ZZ>= ` 2 ) /\ x e. ( 0..^ N ) ) -> ( 0 gcd N ) =/= 1 )
57	7	oveq1d 5741	. . . . . . . . . . . . . 14 |- ( x e. { 0 } -> ( x gcd N ) = ( 0 gcd N ) )
58	57, 17	eleq2s 2207	. . . . . . . . . . . . 13 |- ( x e. ( 0..^ 1 ) -> ( x gcd N ) = ( 0 gcd N ) )
59	58	neeq1d 2298	. . . . . . . . . . . 12 |- ( x e. ( 0..^ 1 ) -> ( ( x gcd N ) =/= 1 <-> ( 0 gcd N ) =/= 1 ) )
60	56, 59	syl5ibrcom 156	. . . . . . . . . . 11 |- ( ( N e. ( ZZ>= ` 2 ) /\ x e. ( 0..^ N ) ) -> ( x e. ( 0..^ 1 ) -> ( x gcd N ) =/= 1 ) )
61	60	necon2bd 2338	. . . . . . . . . 10 |- ( ( N e. ( ZZ>= ` 2 ) /\ x e. ( 0..^ N ) ) -> ( ( x gcd N ) = 1 -> -. x e. ( 0..^ 1 ) ) )
62		simpr 109	. . . . . . . . . . . 12 |- ( ( N e. ( ZZ>= ` 2 ) /\ x e. ( 0..^ N ) ) -> x e. ( 0..^ N ) )
63		1z 8978	. . . . . . . . . . . 12 |- 1 e. ZZ
64		fzospliti 9840	. . . . . . . . . . . 12 |- ( ( x e. ( 0..^ N ) /\ 1 e. ZZ ) -> ( x e. ( 0..^ 1 ) \/ x e. ( 1..^ N ) ) )
65	62, 63, 64	sylancl 407	. . . . . . . . . . 11 |- ( ( N e. ( ZZ>= ` 2 ) /\ x e. ( 0..^ N ) ) -> ( x e. ( 0..^ 1 ) \/ x e. ( 1..^ N ) ) )
66	65	ord 696	. . . . . . . . . 10 |- ( ( N e. ( ZZ>= ` 2 ) /\ x e. ( 0..^ N ) ) -> ( -. x e. ( 0..^ 1 ) -> x e. ( 1..^ N ) ) )
67	61, 66	syld 45	. . . . . . . . 9 |- ( ( N e. ( ZZ>= ` 2 ) /\ x e. ( 0..^ N ) ) -> ( ( x gcd N ) = 1 -> x e. ( 1..^ N ) ) )
68	67	ralrimiva 2477	. . . . . . . 8 |- ( N e. ( ZZ>= ` 2 ) -> A. x e. ( 0..^ N ) ( ( x gcd N ) = 1 -> x e. ( 1..^ N ) ) )
69		rabss 3138	. . . . . . . 8 |- ( { x e. ( 0..^ N ) | ( x gcd N ) = 1 } C_ ( 1..^ N ) <-> A. x e. ( 0..^ N ) ( ( x gcd N ) = 1 -> x e. ( 1..^ N ) ) )
70	68, 69	sylibr 133	. . . . . . 7 |- ( N e. ( ZZ>= ` 2 ) -> { x e. ( 0..^ N ) | ( x gcd N ) = 1 } C_ ( 1..^ N ) )
71		df-ss 3048	. . . . . . 7 |- ( { x e. ( 0..^ N ) | ( x gcd N ) = 1 } C_ ( 1..^ N ) <-> ( { x e. ( 0..^ N ) | ( x gcd N ) = 1 } i^i ( 1..^ N ) ) = { x e. ( 0..^ N ) | ( x gcd N ) = 1 } )
72	70, 71	sylib 121	. . . . . 6 |- ( N e. ( ZZ>= ` 2 ) -> ( { x e. ( 0..^ N ) | ( x gcd N ) = 1 } i^i ( 1..^ N ) ) = { x e. ( 0..^ N ) | ( x gcd N ) = 1 } )
73	38, 45, 72	3eqtr3d 2153	. . . . 5 |- ( N e. ( ZZ>= ` 2 ) -> { x e. ( 1 ... N ) | ( x gcd N ) = 1 } = { x e. ( 0..^ N ) | ( x gcd N ) = 1 } )
74	73	fveq2d 5377	. . . 4 |- ( N e. ( ZZ>= ` 2 ) -> (♯ ` { x e. ( 1 ... N ) | ( x gcd N ) = 1 } ) = (♯ ` { x e. ( 0..^ N ) | ( x gcd N ) = 1 } ) )
75	26, 74	eqtrd 2145	. . 3 |- ( N e. ( ZZ>= ` 2 ) -> ( phi ` N ) = (♯ ` { x e. ( 0..^ N ) | ( x gcd N ) = 1 } ) )
76	23, 75	jaoi 688	. 2 |- ( ( N = 1 \/ N e. ( ZZ>= ` 2 ) ) -> ( phi ` N ) = (♯ ` { x e. ( 0..^ N ) | ( x gcd N ) = 1 } ) )
77	1, 76	sylbi 120	1 |- ( N e. NN -> ( phi ` N ) = (♯ ` { x e. ( 0..^ N ) | ( x gcd N ) = 1 } ) )

Syntax hints:   -. wn 3   -> wi 4   /\ wa 103   \/ wo 680   = wceq 1312   e. wcel 1461   =/= wne 2280   A.wral 2388   {crab 2392   i^i cin 3034   C_ wss 3035   {csn 3491   ` cfv 5079  (class class class)co 5726   0cc0 7541   1c1 7542   - cmin 7850   NNcn 8624   2c2 8675   ZZcz 8952   ZZ>=cuz 9222   ...cfz 9677  ..^cfzo 9806  ♯chash 10408   abscabs 10655   gcd cgcd 11477   phicphi 11725

This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-mp 7  ax-ia1 105  ax-ia2 106  ax-ia3 107  ax-in1 586  ax-in2 587  ax-io 681  ax-5 1404  ax-7 1405  ax-gen 1406  ax-ie1 1450  ax-ie2 1451  ax-8 1463  ax-10 1464  ax-11 1465  ax-i12 1466  ax-bndl 1467  ax-4 1468  ax-13 1472  ax-14 1473  ax-17 1487  ax-i9 1491  ax-ial 1495  ax-i5r 1496  ax-ext 2095  ax-coll 4001  ax-sep 4004  ax-nul 4012  ax-pow 4056  ax-pr 4089  ax-un 4313  ax-setind 4410  ax-iinf 4460  ax-cnex 7630  ax-resscn 7631  ax-1cn 7632  ax-1re 7633  ax-icn 7634  ax-addcl 7635  ax-addrcl 7636  ax-mulcl 7637  ax-mulrcl 7638  ax-addcom 7639  ax-mulcom 7640  ax-addass 7641  ax-mulass 7642  ax-distr 7643  ax-i2m1 7644  ax-0lt1 7645  ax-1rid 7646  ax-0id 7647  ax-rnegex 7648  ax-precex 7649  ax-cnre 7650  ax-pre-ltirr 7651  ax-pre-ltwlin 7652  ax-pre-lttrn 7653  ax-pre-apti 7654  ax-pre-ltadd 7655  ax-pre-mulgt0 7656  ax-pre-mulext 7657  ax-arch 7658  ax-caucvg 7659

This theorem depends on definitions:  df-bi 116  df-stab 799  df-dc 803  df-3or 944  df-3an 945  df-tru 1315  df-fal 1318  df-nf 1418  df-sb 1717  df-eu 1976  df-mo 1977  df-clab 2100  df-cleq 2106  df-clel 2109  df-nfc 2242  df-ne 2281  df-nel 2376  df-ral 2393  df-rex 2394  df-reu 2395  df-rmo 2396  df-rab 2397  df-v 2657  df-sbc 2877  df-csb 2970  df-dif 3037  df-un 3039  df-in 3041  df-ss 3048  df-nul 3328  df-if 3439  df-pw 3476  df-sn 3497  df-pr 3498  df-op 3500  df-uni 3701  df-int 3736  df-iun 3779  df-br 3894  df-opab 3948  df-mpt 3949  df-tr 3985  df-id 4173  df-po 4176  df-iso 4177  df-iord 4246  df-on 4248  df-ilim 4249  df-suc 4251  df-iom 4463  df-xp 4503  df-rel 4504  df-cnv 4505  df-co 4506  df-dm 4507  df-rn 4508  df-res 4509  df-ima 4510  df-iota 5044  df-fun 5081  df-fn 5082  df-f 5083  df-f1 5084  df-fo 5085  df-f1o 5086  df-fv 5087  df-riota 5682  df-ov 5729  df-oprab 5730  df-mpo 5731  df-1st 5990  df-2nd 5991  df-recs 6154  df-frec 6240  df-1o 6265  df-er 6381  df-en 6587  df-dom 6588  df-fin 6589  df-sup 6821  df-pnf 7720  df-mnf 7721  df-xr 7722  df-ltxr 7723  df-le 7724  df-sub 7852  df-neg 7853  df-reap 8249  df-ap 8256  df-div 8340  df-inn 8625  df-2 8683  df-3 8684  df-4 8685  df-n0 8876  df-z 8953  df-uz 9223  df-q 9308  df-rp 9338  df-fz 9678  df-fzo 9807  df-fl 9930  df-mod 9983  df-seqfrec 10106  df-exp 10180  df-ihash 10409  df-cj 10501  df-re 10502  df-im 10503  df-rsqrt 10656  df-abs 10657  df-dvds 11336  df-gcd 11478  df-phi 11726

This theorem is referenced by:  phimullem  11740  hashgcdeq  11743