Theorem 2503lem3 14623

Description: Lemma for 2503prm 14624. 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 10610	. . . 4 |- 2 e. NN
2		1nn0 10728	. . . . 5 |- 1 e. NN0
3		8nn0 10735	. . . . 5 |- 8 e. NN0
4	2, 3	deccl 10909	. . . 4 |- ; 1 8 e. NN0
5		nnexpcl 12082	. . . 4 |- ( ( 2 e. NN /\ ; 1 8 e. NN0 ) -> ( 2 ^; 1 8 ) e. NN )
6	1, 4, 5	mp2an 670	. . 3 |- ( 2 ^; 1 8 ) e. NN
7		nnm1nn0 10754	. . 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 10730	. . . 4 |- 3 e. NN0
10	4, 9	deccl 10909	. . 3 |- ;; 1 8 3 e. NN0
11	10, 2	deccl 10909	. 2 |- ;;; 1 8 3 1 e. NN0
12		2503prm.1	. . 3 |- N = ;;; 2 5 0 3
13		2nn0 10729	. . . . . 6 |- 2 e. NN0
14		5nn0 10732	. . . . . 6 |- 5 e. NN0
15	13, 14	deccl 10909	. . . . 5 |- ; 2 5 e. NN0
16		0nn0 10727	. . . . 5 |- 0 e. NN0
17	15, 16	deccl 10909	. . . 4 |- ;; 2 5 0 e. NN0
18		3nn 10611	. . . 4 |- 3 e. NN
19	17, 18	decnncl 10908	. . 3 |- ;;; 2 5 0 3 e. NN
20	12, 19	eqeltri 2466	. 2 |- N e. NN
21	12	2503lem1 14621	. . 3 |- ( ( 2 ^; 1 8 ) mod N ) = (;;; 1 8 3 2 mod N )
22		1p1e2 10566	. . . 4 |- ( 1 + 1 ) = 2
23		eqid 2382	. . . 4 |- ;;; 1 8 3 1 = ;;; 1 8 3 1
24	10, 2, 22, 23	decsuc 10918	. . 3 |- (;;; 1 8 3 1 + 1 ) = ;;; 1 8 3 2
25	20, 6, 2, 11, 21, 24	modsubi 14560	. 2 |- ( ( ( 2 ^; 1 8 ) - 1 ) mod N ) = (;;; 1 8 3 1 mod N )
26		6nn0 10733	. . . . 5 |- 6 e. NN0
27		7nn0 10734	. . . . 5 |- 7 e. NN0
28	26, 27	deccl 10909	. . . 4 |- ; 6 7 e. NN0
29	28, 13	deccl 10909	. . 3 |- ;; 6 7 2 e. NN0
30		4nn0 10731	. . . . . 6 |- 4 e. NN0
31	30, 3	deccl 10909	. . . . 5 |- ; 4 8 e. NN0
32	31, 27	deccl 10909	. . . 4 |- ;; 4 8 7 e. NN0
33	4, 14	deccl 10909	. . . . 5 |- ;; 1 8 5 e. NN0
34	2, 2	deccl 10909	. . . . . . 7 |- ; 1 1 e. NN0
35	34, 27	deccl 10909	. . . . . 6 |- ;; 1 1 7 e. NN0
36	26, 3	deccl 10909	. . . . . . 7 |- ; 6 8 e. NN0
37		9nn0 10736	. . . . . . . . 9 |- 9 e. NN0
38	30, 37	deccl 10909	. . . . . . . 8 |- ; 4 9 e. NN0
39	2, 37	deccl 10909	. . . . . . . . 9 |- ; 1 9 e. NN0
40	38	nn0zi 10806	. . . . . . . . . . 11 |- ; 4 9 e. ZZ
41	39	nn0zi 10806	. . . . . . . . . . 11 |- ; 1 9 e. ZZ
42		gcdcom 14160	. . . . . . . . . . 11 |- ( (; 4 9 e. ZZ /\ ; 1 9 e. ZZ ) -> (; 4 9 gcd ; 1 9 ) = (; 1 9 gcd ; 4 9 ) )
43	40, 41, 42	mp2an 670	. . . . . . . . . 10 |- (; 4 9 gcd ; 1 9 ) = (; 1 9 gcd ; 4 9 )
44		9nn 10617	. . . . . . . . . . . . 13 |- 9 e. NN
45	2, 44	decnncl 10908	. . . . . . . . . . . 12 |- ; 1 9 e. NN
46		1nn 10463	. . . . . . . . . . . . 13 |- 1 e. NN
47	2, 46	decnncl 10908	. . . . . . . . . . . 12 |- ; 1 1 e. NN
48		eqid 2382	. . . . . . . . . . . . 13 |- ; 1 9 = ; 1 9
49		eqid 2382	. . . . . . . . . . . . 13 |- ; 1 1 = ; 1 1
50		2cn 10523	. . . . . . . . . . . . . . . 16 |- 2 e. CC
51	50	mulid2i 9510	. . . . . . . . . . . . . . 15 |- ( 1 x. 2 ) = 2
52	51, 22	oveq12i 6208	. . . . . . . . . . . . . 14 |- ( ( 1 x. 2 ) + ( 1 + 1 ) ) = ( 2 + 2 )
53		2p2e4 10570	. . . . . . . . . . . . . 14 |- ( 2 + 2 ) = 4
54	52, 53	eqtri 2411	. . . . . . . . . . . . 13 |- ( ( 1 x. 2 ) + ( 1 + 1 ) ) = 4
55		8p1e9 10583	. . . . . . . . . . . . . 14 |- ( 8 + 1 ) = 9
56		9t2e18 10990	. . . . . . . . . . . . . 14 |- ( 9 x. 2 ) = ; 1 8
57	2, 3, 55, 56	decsuc 10918	. . . . . . . . . . . . 13 |- ( ( 9 x. 2 ) + 1 ) = ; 1 9
58	2, 37, 2, 2, 48, 49, 13, 37, 2, 54, 57	decmac 10934	. . . . . . . . . . . 12 |- ( (; 1 9 x. 2 ) + ; 1 1 ) = ; 4 9
59		1lt9 10654	. . . . . . . . . . . . 13 |- 1 < 9
60	2, 2, 44, 59	declt 10916	. . . . . . . . . . . 12 |- ; 1 1 < ; 1 9
61	45, 13, 47, 58, 60	ndvdsi 14070	. . . . . . . . . . 11 |- -. ; 1 9 || ; 4 9
62		19prm 14605	. . . . . . . . . . . 12 |- ; 1 9 e. Prime
63		coprm 14243	. . . . . . . . . . . 12 |- ( (; 1 9 e. Prime /\ ; 4 9 e. ZZ ) -> ( -. ; 1 9 || ; 4 9 <-> (; 1 9 gcd ; 4 9 ) = 1 ) )
64	62, 40, 63	mp2an 670	. . . . . . . . . . 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 2411	. . . . . . . . 9 |- (; 4 9 gcd ; 1 9 ) = 1
67		eqid 2382	. . . . . . . . . 10 |- ; 4 9 = ; 4 9
68		4cn 10530	. . . . . . . . . . . . 13 |- 4 e. CC
69	68	mulid2i 9510	. . . . . . . . . . . 12 |- ( 1 x. 4 ) = 4
70	69, 22	oveq12i 6208	. . . . . . . . . . 11 |- ( ( 1 x. 4 ) + ( 1 + 1 ) ) = ( 4 + 2 )
71		4p2e6 10587	. . . . . . . . . . 11 |- ( 4 + 2 ) = 6
72	70, 71	eqtri 2411	. . . . . . . . . 10 |- ( ( 1 x. 4 ) + ( 1 + 1 ) ) = 6
73		9cn 10540	. . . . . . . . . . . . 13 |- 9 e. CC
74	73	mulid2i 9510	. . . . . . . . . . . 12 |- ( 1 x. 9 ) = 9
75	74	oveq1i 6206	. . . . . . . . . . 11 |- ( ( 1 x. 9 ) + 9 ) = ( 9 + 9 )
76		9p9e18 10964	. . . . . . . . . . 11 |- ( 9 + 9 ) = ; 1 8
77	75, 76	eqtri 2411	. . . . . . . . . 10 |- ( ( 1 x. 9 ) + 9 ) = ; 1 8
78	30, 37, 2, 37, 67, 48, 2, 3, 2, 72, 77	decma2c 10935	. . . . . . . . 9 |- ( ( 1 x. ; 4 9 ) + ; 1 9 ) = ; 6 8
79	2, 39, 38, 66, 78	gcdi 14561	. . . . . . . 8 |- (; 6 8 gcd ; 4 9 ) = 1
80		eqid 2382	. . . . . . . . 9 |- ; 6 8 = ; 6 8
81		6cn 10534	. . . . . . . . . . . 12 |- 6 e. CC
82	81	mulid2i 9510	. . . . . . . . . . 11 |- ( 1 x. 6 ) = 6
83		4p1e5 10579	. . . . . . . . . . 11 |- ( 4 + 1 ) = 5
84	82, 83	oveq12i 6208	. . . . . . . . . 10 |- ( ( 1 x. 6 ) + ( 4 + 1 ) ) = ( 6 + 5 )
85		6p5e11 10945	. . . . . . . . . 10 |- ( 6 + 5 ) = ; 1 1
86	84, 85	eqtri 2411	. . . . . . . . 9 |- ( ( 1 x. 6 ) + ( 4 + 1 ) ) = ; 1 1
87		8cn 10538	. . . . . . . . . . . 12 |- 8 e. CC
88	87	mulid2i 9510	. . . . . . . . . . 11 |- ( 1 x. 8 ) = 8
89	88	oveq1i 6206	. . . . . . . . . 10 |- ( ( 1 x. 8 ) + 9 ) = ( 8 + 9 )
90		9p8e17 10963	. . . . . . . . . . 11 |- ( 9 + 8 ) = ; 1 7
91	73, 87, 90	addcomli 9683	. . . . . . . . . 10 |- ( 8 + 9 ) = ; 1 7
92	89, 91	eqtri 2411	. . . . . . . . 9 |- ( ( 1 x. 8 ) + 9 ) = ; 1 7
93	26, 3, 30, 37, 80, 67, 2, 27, 2, 86, 92	decma2c 10935	. . . . . . . 8 |- ( ( 1 x. ; 6 8 ) + ; 4 9 ) = ;; 1 1 7
94	2, 38, 36, 79, 93	gcdi 14561	. . . . . . 7 |- (;; 1 1 7 gcd ; 6 8 ) = 1
95		eqid 2382	. . . . . . . 8 |- ;; 1 1 7 = ;; 1 1 7
96		6p1e7 10581	. . . . . . . . . 10 |- ( 6 + 1 ) = 7
97	27	dec0h 10911	. . . . . . . . . 10 |- 7 = ; 0 7
98	96, 97	eqtri 2411	. . . . . . . . 9 |- ( 6 + 1 ) = ; 0 7
99		ax-1cn 9461	. . . . . . . . . . . 12 |- 1 e. CC
100	99	mulid1i 9509	. . . . . . . . . . 11 |- ( 1 x. 1 ) = 1
101		00id 9666	. . . . . . . . . . 11 |- ( 0 + 0 ) = 0
102	100, 101	oveq12i 6208	. . . . . . . . . 10 |- ( ( 1 x. 1 ) + ( 0 + 0 ) ) = ( 1 + 0 )
103	99	addid1i 9678	. . . . . . . . . 10 |- ( 1 + 0 ) = 1
104	102, 103	eqtri 2411	. . . . . . . . 9 |- ( ( 1 x. 1 ) + ( 0 + 0 ) ) = 1
105	100	oveq1i 6206	. . . . . . . . . 10 |- ( ( 1 x. 1 ) + 7 ) = ( 1 + 7 )
106		7cn 10536	. . . . . . . . . . 11 |- 7 e. CC
107		7p1e8 10582	. . . . . . . . . . 11 |- ( 7 + 1 ) = 8
108	106, 99, 107	addcomli 9683	. . . . . . . . . 10 |- ( 1 + 7 ) = 8
109	3	dec0h 10911	. . . . . . . . . 10 |- 8 = ; 0 8
110	105, 108, 109	3eqtri 2415	. . . . . . . . 9 |- ( ( 1 x. 1 ) + 7 ) = ; 0 8
111	2, 2, 16, 27, 49, 98, 2, 3, 16, 104, 110	decma2c 10935	. . . . . . . 8 |- ( ( 1 x. ; 1 1 ) + ( 6 + 1 ) ) = ; 1 8
112	106	mulid2i 9510	. . . . . . . . . 10 |- ( 1 x. 7 ) = 7
113	112	oveq1i 6206	. . . . . . . . 9 |- ( ( 1 x. 7 ) + 8 ) = ( 7 + 8 )
114		8p7e15 10955	. . . . . . . . . 10 |- ( 8 + 7 ) = ; 1 5
115	87, 106, 114	addcomli 9683	. . . . . . . . 9 |- ( 7 + 8 ) = ; 1 5
116	113, 115	eqtri 2411	. . . . . . . 8 |- ( ( 1 x. 7 ) + 8 ) = ; 1 5
117	34, 27, 26, 3, 95, 80, 2, 14, 2, 111, 116	decma2c 10935	. . . . . . 7 |- ( ( 1 x. ;; 1 1 7 ) + ; 6 8 ) = ;; 1 8 5
118	2, 36, 35, 94, 117	gcdi 14561	. . . . . 6 |- (;; 1 8 5 gcd ;; 1 1 7 ) = 1
119		eqid 2382	. . . . . . 7 |- ;; 1 8 5 = ;; 1 8 5
120		eqid 2382	. . . . . . . 8 |- ; 1 8 = ; 1 8
121	2, 2, 22, 49	decsuc 10918	. . . . . . . 8 |- (; 1 1 + 1 ) = ; 1 2
122	50	mulid1i 9509	. . . . . . . . . 10 |- ( 2 x. 1 ) = 2
123	122, 22	oveq12i 6208	. . . . . . . . 9 |- ( ( 2 x. 1 ) + ( 1 + 1 ) ) = ( 2 + 2 )
124	123, 53	eqtri 2411	. . . . . . . 8 |- ( ( 2 x. 1 ) + ( 1 + 1 ) ) = 4
125		8t2e16 10983	. . . . . . . . . 10 |- ( 8 x. 2 ) = ; 1 6
126	87, 50, 125	mulcomli 9514	. . . . . . . . 9 |- ( 2 x. 8 ) = ; 1 6
127		6p2e8 10594	. . . . . . . . 9 |- ( 6 + 2 ) = 8
128	2, 26, 13, 126, 127	decaddi 10939	. . . . . . . 8 |- ( ( 2 x. 8 ) + 2 ) = ; 1 8
129	2, 3, 2, 13, 120, 121, 13, 3, 2, 124, 128	decma2c 10935	. . . . . . 7 |- ( ( 2 x. ; 1 8 ) + (; 1 1 + 1 ) ) = ; 4 8
130		5cn 10532	. . . . . . . . . 10 |- 5 e. CC
131		5t2e10 10607	. . . . . . . . . 10 |- ( 5 x. 2 ) = 10
132	130, 50, 131	mulcomli 9514	. . . . . . . . 9 |- ( 2 x. 5 ) = 10
133		dec10 10925	. . . . . . . . 9 |- 10 = ; 1 0
134	132, 133	eqtri 2411	. . . . . . . 8 |- ( 2 x. 5 ) = ; 1 0
135	106	addid2i 9679	. . . . . . . 8 |- ( 0 + 7 ) = 7
136	2, 16, 27, 134, 135	decaddi 10939	. . . . . . 7 |- ( ( 2 x. 5 ) + 7 ) = ; 1 7
137	4, 14, 34, 27, 119, 95, 13, 27, 2, 129, 136	decma2c 10935	. . . . . 6 |- ( ( 2 x. ;; 1 8 5 ) + ;; 1 1 7 ) = ;; 4 8 7
138	13, 35, 33, 118, 137	gcdi 14561	. . . . 5 |- (;; 4 8 7 gcd ;; 1 8 5 ) = 1
139		eqid 2382	. . . . . 6 |- ;; 4 8 7 = ;; 4 8 7
140		eqid 2382	. . . . . . 7 |- ; 4 8 = ; 4 8
141	2, 3, 55, 120	decsuc 10918	. . . . . . 7 |- (; 1 8 + 1 ) = ; 1 9
142	30, 3, 2, 37, 140, 141, 2, 27, 2, 72, 92	decma2c 10935	. . . . . 6 |- ( ( 1 x. ; 4 8 ) + (; 1 8 + 1 ) ) = ; 6 7
143	112	oveq1i 6206	. . . . . . 7 |- ( ( 1 x. 7 ) + 5 ) = ( 7 + 5 )
144		7p5e12 10948	. . . . . . 7 |- ( 7 + 5 ) = ; 1 2
145	143, 144	eqtri 2411	. . . . . 6 |- ( ( 1 x. 7 ) + 5 ) = ; 1 2
146	31, 27, 4, 14, 139, 119, 2, 13, 2, 142, 145	decma2c 10935	. . . . 5 |- ( ( 1 x. ;; 4 8 7 ) + ;; 1 8 5 ) = ;; 6 7 2
147	2, 33, 32, 138, 146	gcdi 14561	. . . 4 |- (;; 6 7 2 gcd ;; 4 8 7 ) = 1
148		eqid 2382	. . . . 5 |- ;; 6 7 2 = ;; 6 7 2
149		eqid 2382	. . . . . 6 |- ; 6 7 = ; 6 7
150	30, 3, 55, 140	decsuc 10918	. . . . . 6 |- (; 4 8 + 1 ) = ; 4 9
151	71	oveq2i 6207	. . . . . . 7 |- ( ( 2 x. 6 ) + ( 4 + 2 ) ) = ( ( 2 x. 6 ) + 6 )
152		6t2e12 10972	. . . . . . . . 9 |- ( 6 x. 2 ) = ; 1 2
153	81, 50, 152	mulcomli 9514	. . . . . . . 8 |- ( 2 x. 6 ) = ; 1 2
154	81, 50, 127	addcomli 9683	. . . . . . . 8 |- ( 2 + 6 ) = 8
155	2, 13, 26, 153, 154	decaddi 10939	. . . . . . 7 |- ( ( 2 x. 6 ) + 6 ) = ; 1 8
156	151, 155	eqtri 2411	. . . . . 6 |- ( ( 2 x. 6 ) + ( 4 + 2 ) ) = ; 1 8
157		7t2e14 10977	. . . . . . . 8 |- ( 7 x. 2 ) = ; 1 4
158	106, 50, 157	mulcomli 9514	. . . . . . 7 |- ( 2 x. 7 ) = ; 1 4
159		9p4e13 10959	. . . . . . . 8 |- ( 9 + 4 ) = ; 1 3
160	73, 68, 159	addcomli 9683	. . . . . . 7 |- ( 4 + 9 ) = ; 1 3
161	2, 30, 37, 158, 22, 9, 160	decaddci 10940	. . . . . 6 |- ( ( 2 x. 7 ) + 9 ) = ; 2 3
162	26, 27, 30, 37, 149, 150, 13, 9, 13, 156, 161	decma2c 10935	. . . . 5 |- ( ( 2 x. ; 6 7 ) + (; 4 8 + 1 ) ) = ;; 1 8 3
163		2t2e4 10602	. . . . . . 7 |- ( 2 x. 2 ) = 4
164	163	oveq1i 6206	. . . . . 6 |- ( ( 2 x. 2 ) + 7 ) = ( 4 + 7 )
165		7p4e11 10947	. . . . . . 7 |- ( 7 + 4 ) = ; 1 1
166	106, 68, 165	addcomli 9683	. . . . . 6 |- ( 4 + 7 ) = ; 1 1
167	164, 166	eqtri 2411	. . . . 5 |- ( ( 2 x. 2 ) + 7 ) = ; 1 1
168	28, 13, 31, 27, 148, 139, 13, 2, 2, 162, 167	decma2c 10935	. . . 4 |- ( ( 2 x. ;; 6 7 2 ) + ;; 4 8 7 ) = ;;; 1 8 3 1
169	13, 32, 29, 147, 168	gcdi 14561	. . 3 |- (;;; 1 8 3 1 gcd ;; 6 7 2 ) = 1
170		eqid 2382	. . . . . 6 |- ;; 1 8 3 = ;; 1 8 3
171	28	nn0cni 10724	. . . . . . 7 |- ; 6 7 e. CC
172	171	addid1i 9678	. . . . . 6 |- (; 6 7 + 0 ) = ; 6 7
173	99	addid2i 9679	. . . . . . . . 9 |- ( 0 + 1 ) = 1
174	100, 173	oveq12i 6208	. . . . . . . 8 |- ( ( 1 x. 1 ) + ( 0 + 1 ) ) = ( 1 + 1 )
175	174, 22	eqtri 2411	. . . . . . 7 |- ( ( 1 x. 1 ) + ( 0 + 1 ) ) = 2
176	88	oveq1i 6206	. . . . . . . 8 |- ( ( 1 x. 8 ) + 7 ) = ( 8 + 7 )
177	176, 114	eqtri 2411	. . . . . . 7 |- ( ( 1 x. 8 ) + 7 ) = ; 1 5
178	2, 3, 16, 27, 120, 98, 2, 14, 2, 175, 177	decma2c 10935	. . . . . 6 |- ( ( 1 x. ; 1 8 ) + ( 6 + 1 ) ) = ; 2 5
179		3cn 10527	. . . . . . . . 9 |- 3 e. CC
180	179	mulid2i 9510	. . . . . . . 8 |- ( 1 x. 3 ) = 3
181	180	oveq1i 6206	. . . . . . 7 |- ( ( 1 x. 3 ) + 7 ) = ( 3 + 7 )
182		7p3e10 10598	. . . . . . . 8 |- ( 7 + 3 ) = 10
183	106, 179, 182	addcomli 9683	. . . . . . 7 |- ( 3 + 7 ) = 10
184	181, 183, 133	3eqtri 2415	. . . . . 6 |- ( ( 1 x. 3 ) + 7 ) = ; 1 0
185	4, 9, 26, 27, 170, 172, 2, 16, 2, 178, 184	decma2c 10935	. . . . 5 |- ( ( 1 x. ;; 1 8 3 ) + (; 6 7 + 0 ) ) = ;; 2 5 0
186	100	oveq1i 6206	. . . . . 6 |- ( ( 1 x. 1 ) + 2 ) = ( 1 + 2 )
187		1p2e3 10577	. . . . . 6 |- ( 1 + 2 ) = 3
188	9	dec0h 10911	. . . . . 6 |- 3 = ; 0 3
189	186, 187, 188	3eqtri 2415	. . . . 5 |- ( ( 1 x. 1 ) + 2 ) = ; 0 3
190	10, 2, 28, 13, 23, 148, 2, 9, 16, 185, 189	decma2c 10935	. . . 4 |- ( ( 1 x. ;;; 1 8 3 1 ) + ;; 6 7 2 ) = ;;; 2 5 0 3
191	190, 12	eqtr4i 2414	. . 3 |- ( ( 1 x. ;;; 1 8 3 1 ) + ;; 6 7 2 ) = N
192	2, 29, 11, 169, 191	gcdi 14561	. 2 |- ( N gcd ;;; 1 8 3 1 ) = 1
193	8, 11, 20, 25, 192	gcdmodi 14562	1 |- ( ( ( 2 ^; 1 8 ) - 1 ) gcd N ) = 1

Syntax hints:   -. wn 3   <-> wb 184   = wceq 1399   e. wcel 1826   class class class wbr 4367  (class class class)co 6196   0cc0 9403   1c1 9404   + caddc 9406   x. cmul 9408   - cmin 9718   NNcn 10452   2c2 10502   3c3 10503   4c4 10504   5c5 10505   6c6 10506   7c7 10507   8c8 10508   9c9 10509   10c10 10510   NN0cn0 10712   ZZcz 10781  ;cdc 10895   ^cexp 12069   || cdvds 13988   gcd cgcd 14146   Primecprime 14219

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1626  ax-4 1639  ax-5 1712  ax-6 1755  ax-7 1798  ax-8 1828  ax-9 1830  ax-10 1845  ax-11 1850  ax-12 1862  ax-13 2006  ax-ext 2360  ax-sep 4488  ax-nul 4496  ax-pow 4543  ax-pr 4601  ax-un 6491  ax-cnex 9459  ax-resscn 9460  ax-1cn 9461  ax-icn 9462  ax-addcl 9463  ax-addrcl 9464  ax-mulcl 9465  ax-mulrcl 9466  ax-mulcom 9467  ax-addass 9468  ax-mulass 9469  ax-distr 9470  ax-i2m1 9471  ax-1ne0 9472  ax-1rid 9473  ax-rnegex 9474  ax-rrecex 9475  ax-cnre 9476  ax-pre-lttri 9477  ax-pre-lttrn 9478  ax-pre-ltadd 9479  ax-pre-mulgt0 9480  ax-pre-sup 9481

This theorem depends on definitions:  df-bi 185  df-or 368  df-an 369  df-3or 972  df-3an 973  df-tru 1402  df-ex 1621  df-nf 1625  df-sb 1748  df-eu 2222  df-mo 2223  df-clab 2368  df-cleq 2374  df-clel 2377  df-nfc 2532  df-ne 2579  df-nel 2580  df-ral 2737  df-rex 2738  df-reu 2739  df-rmo 2740  df-rab 2741  df-v 3036  df-sbc 3253  df-csb 3349  df-dif 3392  df-un 3394  df-in 3396  df-ss 3403  df-pss 3405  df-nul 3712  df-if 3858  df-pw 3929  df-sn 3945  df-pr 3947  df-tp 3949  df-op 3951  df-uni 4164  df-int 4200  df-iun 4245  df-br 4368  df-opab 4426  df-mpt 4427  df-tr 4461  df-eprel 4705  df-id 4709  df-po 4714  df-so 4715  df-fr 4752  df-we 4754  df-ord 4795  df-on 4796  df-lim 4797  df-suc 4798  df-xp 4919  df-rel 4920  df-cnv 4921  df-co 4922  df-dm 4923  df-rn 4924  df-res 4925  df-ima 4926  df-iota 5460  df-fun 5498  df-fn 5499  df-f 5500  df-f1 5501  df-fo 5502  df-f1o 5503  df-fv 5504  df-riota 6158  df-ov 6199  df-oprab 6200  df-mpt2 6201  df-om 6600  df-1st 6699  df-2nd 6700  df-recs 6960  df-rdg 6994  df-1o 7048  df-2o 7049  df-oadd 7052  df-er 7229  df-en 7436  df-dom 7437  df-sdom 7438  df-fin 7439  df-sup 7816  df-pnf 9541  df-mnf 9542  df-xr 9543  df-ltxr 9544  df-le 9545  df-sub 9720  df-neg 9721  df-div 10124  df-nn 10453  df-2 10511  df-3 10512  df-4 10513  df-5 10514  df-6 10515  df-7 10516  df-8 10517  df-9 10518  df-10 10519  df-n0 10713  df-z 10782  df-dec 10896  df-uz 11002  df-rp 11140  df-fz 11594  df-fl 11828  df-mod 11897  df-seq 12011  df-exp 12070  df-cj 12934  df-re 12935  df-im 12936  df-sqrt 13070  df-abs 13071  df-dvds 13989  df-gcd 14147  df-prm 14220

This theorem is referenced by:  2503prm  14624