Theorem 2503lem3 14468

Description: Lemma for 2503prm 14469. Calculate the GCD of 2 ^ 1 8 - 1 == 1 8 3 1 with N = 2 5 0 3. (Contributed by Mario Carneiro, 3-Mar-2014.) (Revised by Mario Carneiro, 20-Apr-2015.)

Hypothesis

Ref	Expression
2503prm.1	|- N = ;;; 2 5 0 3

Assertion

Ref	Expression
2503lem3	|- ( ( ( 2 ^; 1 8 ) - 1 ) gcd N ) = 1

Proof of Theorem 2503lem3

Step	Hyp	Ref	Expression
1		2nn 10682	. . . 4 |- 2 e. NN
2		1nn0 10800	. . . . 5 |- 1 e. NN0
3		8nn0 10807	. . . . 5 |- 8 e. NN0
4	2, 3	deccl 10979	. . . 4 |- ; 1 8 e. NN0
5		nnexpcl 12135	. . . 4 |- ( ( 2 e. NN /\ ; 1 8 e. NN0 ) -> ( 2 ^; 1 8 ) e. NN )
6	1, 4, 5	mp2an 672	. . 3 |- ( 2 ^; 1 8 ) e. NN
7		nnm1nn0 10826	. . 3 |- ( ( 2 ^; 1 8 ) e. NN -> ( ( 2 ^; 1 8 ) - 1 ) e. NN0 )
8	6, 7	ax-mp 5	. 2 |- ( ( 2 ^; 1 8 ) - 1 ) e. NN0
9		3nn0 10802	. . . 4 |- 3 e. NN0
10	4, 9	deccl 10979	. . 3 |- ;; 1 8 3 e. NN0
11	10, 2	deccl 10979	. 2 |- ;;; 1 8 3 1 e. NN0
12		2503prm.1	. . 3 |- N = ;;; 2 5 0 3
13		2nn0 10801	. . . . . 6 |- 2 e. NN0
14		5nn0 10804	. . . . . 6 |- 5 e. NN0
15	13, 14	deccl 10979	. . . . 5 |- ; 2 5 e. NN0
16		0nn0 10799	. . . . 5 |- 0 e. NN0
17	15, 16	deccl 10979	. . . 4 |- ;; 2 5 0 e. NN0
18		3nn 10683	. . . 4 |- 3 e. NN
19	17, 18	decnncl 10978	. . 3 |- ;;; 2 5 0 3 e. NN
20	12, 19	eqeltri 2544	. 2 |- N e. NN
21	12	2503lem1 14466	. . 3 |- ( ( 2 ^; 1 8 ) mod N ) = (;;; 1 8 3 2 mod N )
22		1p1e2 10638	. . . 4 |- ( 1 + 1 ) = 2
23		eqid 2460	. . . 4 |- ;;; 1 8 3 1 = ;;; 1 8 3 1
24	10, 2, 22, 23	decsuc 10988	. . 3 |- (;;; 1 8 3 1 + 1 ) = ;;; 1 8 3 2
25	20, 6, 2, 11, 21, 24	modsubi 14406	. 2 |- ( ( ( 2 ^; 1 8 ) - 1 ) mod N ) = (;;; 1 8 3 1 mod N )
26		6nn0 10805	. . . . 5 |- 6 e. NN0
27		7nn0 10806	. . . . 5 |- 7 e. NN0
28	26, 27	deccl 10979	. . . 4 |- ; 6 7 e. NN0
29	28, 13	deccl 10979	. . 3 |- ;; 6 7 2 e. NN0
30		4nn0 10803	. . . . . 6 |- 4 e. NN0
31	30, 3	deccl 10979	. . . . 5 |- ; 4 8 e. NN0
32	31, 27	deccl 10979	. . . 4 |- ;; 4 8 7 e. NN0
33	4, 14	deccl 10979	. . . . 5 |- ;; 1 8 5 e. NN0
34	2, 2	deccl 10979	. . . . . . 7 |- ; 1 1 e. NN0
35	34, 27	deccl 10979	. . . . . 6 |- ;; 1 1 7 e. NN0
36	26, 3	deccl 10979	. . . . . . 7 |- ; 6 8 e. NN0
37		9nn0 10808	. . . . . . . . 9 |- 9 e. NN0
38	30, 37	deccl 10979	. . . . . . . 8 |- ; 4 9 e. NN0
39	2, 37	deccl 10979	. . . . . . . . 9 |- ; 1 9 e. NN0
40	38	nn0zi 10878	. . . . . . . . . . 11 |- ; 4 9 e. ZZ
41	39	nn0zi 10878	. . . . . . . . . . 11 |- ; 1 9 e. ZZ
42		gcdcom 14006	. . . . . . . . . . 11 |- ( (; 4 9 e. ZZ /\ ; 1 9 e. ZZ ) -> (; 4 9 gcd ; 1 9 ) = (; 1 9 gcd ; 4 9 ) )
43	40, 41, 42	mp2an 672	. . . . . . . . . 10 |- (; 4 9 gcd ; 1 9 ) = (; 1 9 gcd ; 4 9 )
44		9nn 10689	. . . . . . . . . . . . 13 |- 9 e. NN
45	2, 44	decnncl 10978	. . . . . . . . . . . 12 |- ; 1 9 e. NN
46		1nn 10536	. . . . . . . . . . . . 13 |- 1 e. NN
47	2, 46	decnncl 10978	. . . . . . . . . . . 12 |- ; 1 1 e. NN
48		eqid 2460	. . . . . . . . . . . . 13 |- ; 1 9 = ; 1 9
49		eqid 2460	. . . . . . . . . . . . 13 |- ; 1 1 = ; 1 1
50		2cn 10595	. . . . . . . . . . . . . . . 16 |- 2 e. CC
51	50	mulid2i 9588	. . . . . . . . . . . . . . 15 |- ( 1 x. 2 ) = 2
52	51, 22	oveq12i 6287	. . . . . . . . . . . . . 14 |- ( ( 1 x. 2 ) + ( 1 + 1 ) ) = ( 2 + 2 )
53		2p2e4 10642	. . . . . . . . . . . . . 14 |- ( 2 + 2 ) = 4
54	52, 53	eqtri 2489	. . . . . . . . . . . . 13 |- ( ( 1 x. 2 ) + ( 1 + 1 ) ) = 4
55		8p1e9 10655	. . . . . . . . . . . . . 14 |- ( 8 + 1 ) = 9
56		9t2e18 11060	. . . . . . . . . . . . . 14 |- ( 9 x. 2 ) = ; 1 8
57	2, 3, 55, 56	decsuc 10988	. . . . . . . . . . . . 13 |- ( ( 9 x. 2 ) + 1 ) = ; 1 9
58	2, 37, 2, 2, 48, 49, 13, 37, 2, 54, 57	decmac 11004	. . . . . . . . . . . 12 |- ( (; 1 9 x. 2 ) + ; 1 1 ) = ; 4 9
59		1lt9 10726	. . . . . . . . . . . . 13 |- 1 < 9
60	2, 2, 44, 59	declt 10986	. . . . . . . . . . . 12 |- ; 1 1 < ; 1 9
61	45, 13, 47, 58, 60	ndvdsi 13916	. . . . . . . . . . 11 |- -. ; 1 9 || ; 4 9
62		19prm 14450	. . . . . . . . . . . 12 |- ; 1 9 e. Prime
63		coprm 14089	. . . . . . . . . . . 12 |- ( (; 1 9 e. Prime /\ ; 4 9 e. ZZ ) -> ( -. ; 1 9 || ; 4 9 <-> (; 1 9 gcd ; 4 9 ) = 1 ) )
64	62, 40, 63	mp2an 672	. . . . . . . . . . 11 |- ( -. ; 1 9 || ; 4 9 <-> (; 1 9 gcd ; 4 9 ) = 1 )
65	61, 64	mpbi 208	. . . . . . . . . 10 |- (; 1 9 gcd ; 4 9 ) = 1
66	43, 65	eqtri 2489	. . . . . . . . 9 |- (; 4 9 gcd ; 1 9 ) = 1
67		eqid 2460	. . . . . . . . . 10 |- ; 4 9 = ; 4 9
68		4cn 10602	. . . . . . . . . . . . 13 |- 4 e. CC
69	68	mulid2i 9588	. . . . . . . . . . . 12 |- ( 1 x. 4 ) = 4
70	69, 22	oveq12i 6287	. . . . . . . . . . 11 |- ( ( 1 x. 4 ) + ( 1 + 1 ) ) = ( 4 + 2 )
71		4p2e6 10659	. . . . . . . . . . 11 |- ( 4 + 2 ) = 6
72	70, 71	eqtri 2489	. . . . . . . . . 10 |- ( ( 1 x. 4 ) + ( 1 + 1 ) ) = 6
73		9cn 10612	. . . . . . . . . . . . 13 |- 9 e. CC
74	73	mulid2i 9588	. . . . . . . . . . . 12 |- ( 1 x. 9 ) = 9
75	74	oveq1i 6285	. . . . . . . . . . 11 |- ( ( 1 x. 9 ) + 9 ) = ( 9 + 9 )
76		9p9e18 11034	. . . . . . . . . . 11 |- ( 9 + 9 ) = ; 1 8
77	75, 76	eqtri 2489	. . . . . . . . . 10 |- ( ( 1 x. 9 ) + 9 ) = ; 1 8
78	30, 37, 2, 37, 67, 48, 2, 3, 2, 72, 77	decma2c 11005	. . . . . . . . 9 |- ( ( 1 x. ; 4 9 ) + ; 1 9 ) = ; 6 8
79	2, 39, 38, 66, 78	gcdi 14407	. . . . . . . 8 |- (; 6 8 gcd ; 4 9 ) = 1
80		eqid 2460	. . . . . . . . 9 |- ; 6 8 = ; 6 8
81		6cn 10606	. . . . . . . . . . . 12 |- 6 e. CC
82	81	mulid2i 9588	. . . . . . . . . . 11 |- ( 1 x. 6 ) = 6
83		4p1e5 10651	. . . . . . . . . . 11 |- ( 4 + 1 ) = 5
84	82, 83	oveq12i 6287	. . . . . . . . . 10 |- ( ( 1 x. 6 ) + ( 4 + 1 ) ) = ( 6 + 5 )
85		6p5e11 11015	. . . . . . . . . 10 |- ( 6 + 5 ) = ; 1 1
86	84, 85	eqtri 2489	. . . . . . . . 9 |- ( ( 1 x. 6 ) + ( 4 + 1 ) ) = ; 1 1
87		8cn 10610	. . . . . . . . . . . 12 |- 8 e. CC
88	87	mulid2i 9588	. . . . . . . . . . 11 |- ( 1 x. 8 ) = 8
89	88	oveq1i 6285	. . . . . . . . . 10 |- ( ( 1 x. 8 ) + 9 ) = ( 8 + 9 )
90		9p8e17 11033	. . . . . . . . . . 11 |- ( 9 + 8 ) = ; 1 7
91	73, 87, 90	addcomli 9760	. . . . . . . . . 10 |- ( 8 + 9 ) = ; 1 7
92	89, 91	eqtri 2489	. . . . . . . . 9 |- ( ( 1 x. 8 ) + 9 ) = ; 1 7
93	26, 3, 30, 37, 80, 67, 2, 27, 2, 86, 92	decma2c 11005	. . . . . . . 8 |- ( ( 1 x. ; 6 8 ) + ; 4 9 ) = ;; 1 1 7
94	2, 38, 36, 79, 93	gcdi 14407	. . . . . . 7 |- (;; 1 1 7 gcd ; 6 8 ) = 1
95		eqid 2460	. . . . . . . 8 |- ;; 1 1 7 = ;; 1 1 7
96		6p1e7 10653	. . . . . . . . . 10 |- ( 6 + 1 ) = 7
97	27	dec0h 10981	. . . . . . . . . 10 |- 7 = ; 0 7
98	96, 97	eqtri 2489	. . . . . . . . 9 |- ( 6 + 1 ) = ; 0 7
99		ax-1cn 9539	. . . . . . . . . . . 12 |- 1 e. CC
100	99	mulid1i 9587	. . . . . . . . . . 11 |- ( 1 x. 1 ) = 1
101		00id 9743	. . . . . . . . . . 11 |- ( 0 + 0 ) = 0
102	100, 101	oveq12i 6287	. . . . . . . . . 10 |- ( ( 1 x. 1 ) + ( 0 + 0 ) ) = ( 1 + 0 )
103	99	addid1i 9755	. . . . . . . . . 10 |- ( 1 + 0 ) = 1
104	102, 103	eqtri 2489	. . . . . . . . 9 |- ( ( 1 x. 1 ) + ( 0 + 0 ) ) = 1
105	100	oveq1i 6285	. . . . . . . . . 10 |- ( ( 1 x. 1 ) + 7 ) = ( 1 + 7 )
106		7cn 10608	. . . . . . . . . . 11 |- 7 e. CC
107		7p1e8 10654	. . . . . . . . . . 11 |- ( 7 + 1 ) = 8
108	106, 99, 107	addcomli 9760	. . . . . . . . . 10 |- ( 1 + 7 ) = 8
109	3	dec0h 10981	. . . . . . . . . 10 |- 8 = ; 0 8
110	105, 108, 109	3eqtri 2493	. . . . . . . . 9 |- ( ( 1 x. 1 ) + 7 ) = ; 0 8
111	2, 2, 16, 27, 49, 98, 2, 3, 16, 104, 110	decma2c 11005	. . . . . . . 8 |- ( ( 1 x. ; 1 1 ) + ( 6 + 1 ) ) = ; 1 8
112	106	mulid2i 9588	. . . . . . . . . 10 |- ( 1 x. 7 ) = 7
113	112	oveq1i 6285	. . . . . . . . 9 |- ( ( 1 x. 7 ) + 8 ) = ( 7 + 8 )
114		8p7e15 11025	. . . . . . . . . 10 |- ( 8 + 7 ) = ; 1 5
115	87, 106, 114	addcomli 9760	. . . . . . . . 9 |- ( 7 + 8 ) = ; 1 5
116	113, 115	eqtri 2489	. . . . . . . 8 |- ( ( 1 x. 7 ) + 8 ) = ; 1 5
117	34, 27, 26, 3, 95, 80, 2, 14, 2, 111, 116	decma2c 11005	. . . . . . 7 |- ( ( 1 x. ;; 1 1 7 ) + ; 6 8 ) = ;; 1 8 5
118	2, 36, 35, 94, 117	gcdi 14407	. . . . . 6 |- (;; 1 8 5 gcd ;; 1 1 7 ) = 1
119		eqid 2460	. . . . . . 7 |- ;; 1 8 5 = ;; 1 8 5
120		eqid 2460	. . . . . . . 8 |- ; 1 8 = ; 1 8
121	2, 2, 22, 49	decsuc 10988	. . . . . . . 8 |- (; 1 1 + 1 ) = ; 1 2
122	50	mulid1i 9587	. . . . . . . . . 10 |- ( 2 x. 1 ) = 2
123	122, 22	oveq12i 6287	. . . . . . . . 9 |- ( ( 2 x. 1 ) + ( 1 + 1 ) ) = ( 2 + 2 )
124	123, 53	eqtri 2489	. . . . . . . 8 |- ( ( 2 x. 1 ) + ( 1 + 1 ) ) = 4
125		8t2e16 11053	. . . . . . . . . 10 |- ( 8 x. 2 ) = ; 1 6
126	87, 50, 125	mulcomli 9592	. . . . . . . . 9 |- ( 2 x. 8 ) = ; 1 6
127		6p2e8 10666	. . . . . . . . 9 |- ( 6 + 2 ) = 8
128	2, 26, 13, 126, 127	decaddi 11009	. . . . . . . 8 |- ( ( 2 x. 8 ) + 2 ) = ; 1 8
129	2, 3, 2, 13, 120, 121, 13, 3, 2, 124, 128	decma2c 11005	. . . . . . 7 |- ( ( 2 x. ; 1 8 ) + (; 1 1 + 1 ) ) = ; 4 8
130		5cn 10604	. . . . . . . . . 10 |- 5 e. CC
131		5t2e10 10679	. . . . . . . . . 10 |- ( 5 x. 2 ) = 10
132	130, 50, 131	mulcomli 9592	. . . . . . . . 9 |- ( 2 x. 5 ) = 10
133		dec10 10995	. . . . . . . . 9 |- 10 = ; 1 0
134	132, 133	eqtri 2489	. . . . . . . 8 |- ( 2 x. 5 ) = ; 1 0
135	106	addid2i 9756	. . . . . . . 8 |- ( 0 + 7 ) = 7
136	2, 16, 27, 134, 135	decaddi 11009	. . . . . . 7 |- ( ( 2 x. 5 ) + 7 ) = ; 1 7
137	4, 14, 34, 27, 119, 95, 13, 27, 2, 129, 136	decma2c 11005	. . . . . 6 |- ( ( 2 x. ;; 1 8 5 ) + ;; 1 1 7 ) = ;; 4 8 7
138	13, 35, 33, 118, 137	gcdi 14407	. . . . 5 |- (;; 4 8 7 gcd ;; 1 8 5 ) = 1
139		eqid 2460	. . . . . 6 |- ;; 4 8 7 = ;; 4 8 7
140		eqid 2460	. . . . . . 7 |- ; 4 8 = ; 4 8
141	2, 3, 55, 120	decsuc 10988	. . . . . . 7 |- (; 1 8 + 1 ) = ; 1 9
142	30, 3, 2, 37, 140, 141, 2, 27, 2, 72, 92	decma2c 11005	. . . . . 6 |- ( ( 1 x. ; 4 8 ) + (; 1 8 + 1 ) ) = ; 6 7
143	112	oveq1i 6285	. . . . . . 7 |- ( ( 1 x. 7 ) + 5 ) = ( 7 + 5 )
144		7p5e12 11018	. . . . . . 7 |- ( 7 + 5 ) = ; 1 2
145	143, 144	eqtri 2489	. . . . . 6 |- ( ( 1 x. 7 ) + 5 ) = ; 1 2
146	31, 27, 4, 14, 139, 119, 2, 13, 2, 142, 145	decma2c 11005	. . . . 5 |- ( ( 1 x. ;; 4 8 7 ) + ;; 1 8 5 ) = ;; 6 7 2
147	2, 33, 32, 138, 146	gcdi 14407	. . . 4 |- (;; 6 7 2 gcd ;; 4 8 7 ) = 1
148		eqid 2460	. . . . 5 |- ;; 6 7 2 = ;; 6 7 2
149		eqid 2460	. . . . . 6 |- ; 6 7 = ; 6 7
150	30, 3, 55, 140	decsuc 10988	. . . . . 6 |- (; 4 8 + 1 ) = ; 4 9
151	71	oveq2i 6286	. . . . . . 7 |- ( ( 2 x. 6 ) + ( 4 + 2 ) ) = ( ( 2 x. 6 ) + 6 )
152		6t2e12 11042	. . . . . . . . 9 |- ( 6 x. 2 ) = ; 1 2
153	81, 50, 152	mulcomli 9592	. . . . . . . 8 |- ( 2 x. 6 ) = ; 1 2
154	81, 50, 127	addcomli 9760	. . . . . . . 8 |- ( 2 + 6 ) = 8
155	2, 13, 26, 153, 154	decaddi 11009	. . . . . . 7 |- ( ( 2 x. 6 ) + 6 ) = ; 1 8
156	151, 155	eqtri 2489	. . . . . 6 |- ( ( 2 x. 6 ) + ( 4 + 2 ) ) = ; 1 8
157		7t2e14 11047	. . . . . . . 8 |- ( 7 x. 2 ) = ; 1 4
158	106, 50, 157	mulcomli 9592	. . . . . . 7 |- ( 2 x. 7 ) = ; 1 4
159		9p4e13 11029	. . . . . . . 8 |- ( 9 + 4 ) = ; 1 3
160	73, 68, 159	addcomli 9760	. . . . . . 7 |- ( 4 + 9 ) = ; 1 3
161	2, 30, 37, 158, 22, 9, 160	decaddci 11010	. . . . . 6 |- ( ( 2 x. 7 ) + 9 ) = ; 2 3
162	26, 27, 30, 37, 149, 150, 13, 9, 13, 156, 161	decma2c 11005	. . . . 5 |- ( ( 2 x. ; 6 7 ) + (; 4 8 + 1 ) ) = ;; 1 8 3
163		2t2e4 10674	. . . . . . 7 |- ( 2 x. 2 ) = 4
164	163	oveq1i 6285	. . . . . 6 |- ( ( 2 x. 2 ) + 7 ) = ( 4 + 7 )
165		7p4e11 11017	. . . . . . 7 |- ( 7 + 4 ) = ; 1 1
166	106, 68, 165	addcomli 9760	. . . . . 6 |- ( 4 + 7 ) = ; 1 1
167	164, 166	eqtri 2489	. . . . 5 |- ( ( 2 x. 2 ) + 7 ) = ; 1 1
168	28, 13, 31, 27, 148, 139, 13, 2, 2, 162, 167	decma2c 11005	. . . 4 |- ( ( 2 x. ;; 6 7 2 ) + ;; 4 8 7 ) = ;;; 1 8 3 1
169	13, 32, 29, 147, 168	gcdi 14407	. . 3 |- (;;; 1 8 3 1 gcd ;; 6 7 2 ) = 1
170		eqid 2460	. . . . . 6 |- ;; 1 8 3 = ;; 1 8 3
171	28	nn0cni 10796	. . . . . . 7 |- ; 6 7 e. CC
172	171	addid1i 9755	. . . . . 6 |- (; 6 7 + 0 ) = ; 6 7
173	99	addid2i 9756	. . . . . . . . 9 |- ( 0 + 1 ) = 1
174	100, 173	oveq12i 6287	. . . . . . . 8 |- ( ( 1 x. 1 ) + ( 0 + 1 ) ) = ( 1 + 1 )
175	174, 22	eqtri 2489	. . . . . . 7 |- ( ( 1 x. 1 ) + ( 0 + 1 ) ) = 2
176	88	oveq1i 6285	. . . . . . . 8 |- ( ( 1 x. 8 ) + 7 ) = ( 8 + 7 )
177	176, 114	eqtri 2489	. . . . . . 7 |- ( ( 1 x. 8 ) + 7 ) = ; 1 5
178	2, 3, 16, 27, 120, 98, 2, 14, 2, 175, 177	decma2c 11005	. . . . . 6 |- ( ( 1 x. ; 1 8 ) + ( 6 + 1 ) ) = ; 2 5
179		3cn 10599	. . . . . . . . 9 |- 3 e. CC
180	179	mulid2i 9588	. . . . . . . 8 |- ( 1 x. 3 ) = 3
181	180	oveq1i 6285	. . . . . . 7 |- ( ( 1 x. 3 ) + 7 ) = ( 3 + 7 )
182		7p3e10 10670	. . . . . . . 8 |- ( 7 + 3 ) = 10
183	106, 179, 182	addcomli 9760	. . . . . . 7 |- ( 3 + 7 ) = 10
184	181, 183, 133	3eqtri 2493	. . . . . 6 |- ( ( 1 x. 3 ) + 7 ) = ; 1 0
185	4, 9, 26, 27, 170, 172, 2, 16, 2, 178, 184	decma2c 11005	. . . . 5 |- ( ( 1 x. ;; 1 8 3 ) + (; 6 7 + 0 ) ) = ;; 2 5 0
186	100	oveq1i 6285	. . . . . 6 |- ( ( 1 x. 1 ) + 2 ) = ( 1 + 2 )
187		1p2e3 10649	. . . . . 6 |- ( 1 + 2 ) = 3
188	9	dec0h 10981	. . . . . 6 |- 3 = ; 0 3
189	186, 187, 188	3eqtri 2493	. . . . 5 |- ( ( 1 x. 1 ) + 2 ) = ; 0 3
190	10, 2, 28, 13, 23, 148, 2, 9, 16, 185, 189	decma2c 11005	. . . 4 |- ( ( 1 x. ;;; 1 8 3 1 ) + ;; 6 7 2 ) = ;;; 2 5 0 3
191	190, 12	eqtr4i 2492	. . 3 |- ( ( 1 x. ;;; 1 8 3 1 ) + ;; 6 7 2 ) = N
192	2, 29, 11, 169, 191	gcdi 14407	. 2 |- ( N gcd ;;; 1 8 3 1 ) = 1
193	8, 11, 20, 25, 192	gcdmodi 14408	1 |- ( ( ( 2 ^; 1 8 ) - 1 ) gcd N ) = 1

Syntax hints:   -. wn 3   <-> wb 184   = wceq 1374   e. wcel 1762   class class class wbr 4440  (class class class)co 6275   0cc0 9481   1c1 9482   + caddc 9484   x. cmul 9486   - cmin 9794   NNcn 10525   2c2 10574   3c3 10575   4c4 10576   5c5 10577   6c6 10578   7c7 10579   8c8 10580   9c9 10581   10c10 10582   NN0cn0 10784   ZZcz 10853  ;cdc 10965   ^cexp 12122   || cdivides 13836   gcd cgcd 13992   Primecprime 14065

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1596  ax-4 1607  ax-5 1675  ax-6 1714  ax-7 1734  ax-8 1764  ax-9 1766  ax-10 1781  ax-11 1786  ax-12 1798  ax-13 1961  ax-ext 2438  ax-sep 4561  ax-nul 4569  ax-pow 4618  ax-pr 4679  ax-un 6567  ax-cnex 9537  ax-resscn 9538  ax-1cn 9539  ax-icn 9540  ax-addcl 9541  ax-addrcl 9542  ax-mulcl 9543  ax-mulrcl 9544  ax-mulcom 9545  ax-addass 9546  ax-mulass 9547  ax-distr 9548  ax-i2m1 9549  ax-1ne0 9550  ax-1rid 9551  ax-rnegex 9552  ax-rrecex 9553  ax-cnre 9554  ax-pre-lttri 9555  ax-pre-lttrn 9556  ax-pre-ltadd 9557  ax-pre-mulgt0 9558  ax-pre-sup 9559

This theorem depends on definitions:  df-bi 185  df-or 370  df-an 371  df-3or 969  df-3an 970  df-tru 1377  df-ex 1592  df-nf 1595  df-sb 1707  df-eu 2272  df-mo 2273  df-clab 2446  df-cleq 2452  df-clel 2455  df-nfc 2610  df-ne 2657  df-nel 2658  df-ral 2812  df-rex 2813  df-reu 2814  df-rmo 2815  df-rab 2816  df-v 3108  df-sbc 3325  df-csb 3429  df-dif 3472  df-un 3474  df-in 3476  df-ss 3483  df-pss 3485  df-nul 3779  df-if 3933  df-pw 4005  df-sn 4021  df-pr 4023  df-tp 4025  df-op 4027  df-uni 4239  df-int 4276  df-iun 4320  df-br 4441  df-opab 4499  df-mpt 4500  df-tr 4534  df-eprel 4784  df-id 4788  df-po 4793  df-so 4794  df-fr 4831  df-we 4833  df-ord 4874  df-on 4875  df-lim 4876  df-suc 4877  df-xp 4998  df-rel 4999  df-cnv 5000  df-co 5001  df-dm 5002  df-rn 5003  df-res 5004  df-ima 5005  df-iota 5542  df-fun 5581  df-fn 5582  df-f 5583  df-f1 5584  df-fo 5585  df-f1o 5586  df-fv 5587  df-riota 6236  df-ov 6278  df-oprab 6279  df-mpt2 6280  df-om 6672  df-1st 6774  df-2nd 6775  df-recs 7032  df-rdg 7066  df-1o 7120  df-2o 7121  df-oadd 7124  df-er 7301  df-en 7507  df-dom 7508  df-sdom 7509  df-fin 7510  df-sup 7890  df-pnf 9619  df-mnf 9620  df-xr 9621  df-ltxr 9622  df-le 9623  df-sub 9796  df-neg 9797  df-div 10196  df-nn 10526  df-2 10583  df-3 10584  df-4 10585  df-5 10586  df-6 10587  df-7 10588  df-8 10589  df-9 10590  df-10 10591  df-n0 10785  df-z 10854  df-dec 10966  df-uz 11072  df-rp 11210  df-fz 11662  df-fl 11886  df-mod 11953  df-seq 12064  df-exp 12123  df-cj 12882  df-re 12883  df-im 12884  df-sqr 13018  df-abs 13019  df-dvds 13837  df-gcd 13993  df-prm 14066

This theorem is referenced by:  2503prm  14469