Theorem 2503lem3 15110

Description: Lemma for 2503prm 15111. 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 10767	. . . 4 |- 2 e. NN
2		1nn0 10885	. . . . 5 |- 1 e. NN0
3		8nn0 10892	. . . . 5 |- 8 e. NN0
4	2, 3	deccl 11065	. . . 4 |- ; 1 8 e. NN0
5		nnexpcl 12285	. . . 4 |- ( ( 2 e. NN /\ ; 1 8 e. NN0 ) -> ( 2 ^; 1 8 ) e. NN )
6	1, 4, 5	mp2an 678	. . 3 |- ( 2 ^; 1 8 ) e. NN
7		nnm1nn0 10911	. . 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 10887	. . . 4 |- 3 e. NN0
10	4, 9	deccl 11065	. . 3 |- ;; 1 8 3 e. NN0
11	10, 2	deccl 11065	. 2 |- ;;; 1 8 3 1 e. NN0
12		2503prm.1	. . 3 |- N = ;;; 2 5 0 3
13		2nn0 10886	. . . . . 6 |- 2 e. NN0
14		5nn0 10889	. . . . . 6 |- 5 e. NN0
15	13, 14	deccl 11065	. . . . 5 |- ; 2 5 e. NN0
16		0nn0 10884	. . . . 5 |- 0 e. NN0
17	15, 16	deccl 11065	. . . 4 |- ;; 2 5 0 e. NN0
18		3nn 10768	. . . 4 |- 3 e. NN
19	17, 18	decnncl 11064	. . 3 |- ;;; 2 5 0 3 e. NN
20	12, 19	eqeltri 2525	. 2 |- N e. NN
21	12	2503lem1 15108	. . 3 |- ( ( 2 ^; 1 8 ) mod N ) = (;;; 1 8 3 2 mod N )
22		1p1e2 10723	. . . 4 |- ( 1 + 1 ) = 2
23		eqid 2451	. . . 4 |- ;;; 1 8 3 1 = ;;; 1 8 3 1
24	10, 2, 22, 23	decsuc 11074	. . 3 |- (;;; 1 8 3 1 + 1 ) = ;;; 1 8 3 2
25	20, 6, 2, 11, 21, 24	modsubi 15044	. 2 |- ( ( ( 2 ^; 1 8 ) - 1 ) mod N ) = (;;; 1 8 3 1 mod N )
26		6nn0 10890	. . . . 5 |- 6 e. NN0
27		7nn0 10891	. . . . 5 |- 7 e. NN0
28	26, 27	deccl 11065	. . . 4 |- ; 6 7 e. NN0
29	28, 13	deccl 11065	. . 3 |- ;; 6 7 2 e. NN0
30		4nn0 10888	. . . . . 6 |- 4 e. NN0
31	30, 3	deccl 11065	. . . . 5 |- ; 4 8 e. NN0
32	31, 27	deccl 11065	. . . 4 |- ;; 4 8 7 e. NN0
33	4, 14	deccl 11065	. . . . 5 |- ;; 1 8 5 e. NN0
34	2, 2	deccl 11065	. . . . . . 7 |- ; 1 1 e. NN0
35	34, 27	deccl 11065	. . . . . 6 |- ;; 1 1 7 e. NN0
36	26, 3	deccl 11065	. . . . . . 7 |- ; 6 8 e. NN0
37		9nn0 10893	. . . . . . . . 9 |- 9 e. NN0
38	30, 37	deccl 11065	. . . . . . . 8 |- ; 4 9 e. NN0
39	2, 37	deccl 11065	. . . . . . . . 9 |- ; 1 9 e. NN0
40	38	nn0zi 10962	. . . . . . . . . . 11 |- ; 4 9 e. ZZ
41	39	nn0zi 10962	. . . . . . . . . . 11 |- ; 1 9 e. ZZ
42		gcdcom 14484	. . . . . . . . . . 11 |- ( (; 4 9 e. ZZ /\ ; 1 9 e. ZZ ) -> (; 4 9 gcd ; 1 9 ) = (; 1 9 gcd ; 4 9 ) )
43	40, 41, 42	mp2an 678	. . . . . . . . . 10 |- (; 4 9 gcd ; 1 9 ) = (; 1 9 gcd ; 4 9 )
44		9nn 10774	. . . . . . . . . . . . 13 |- 9 e. NN
45	2, 44	decnncl 11064	. . . . . . . . . . . 12 |- ; 1 9 e. NN
46		1nn 10620	. . . . . . . . . . . . 13 |- 1 e. NN
47	2, 46	decnncl 11064	. . . . . . . . . . . 12 |- ; 1 1 e. NN
48		eqid 2451	. . . . . . . . . . . . 13 |- ; 1 9 = ; 1 9
49		eqid 2451	. . . . . . . . . . . . 13 |- ; 1 1 = ; 1 1
50		2cn 10680	. . . . . . . . . . . . . . . 16 |- 2 e. CC
51	50	mulid2i 9646	. . . . . . . . . . . . . . 15 |- ( 1 x. 2 ) = 2
52	51, 22	oveq12i 6302	. . . . . . . . . . . . . 14 |- ( ( 1 x. 2 ) + ( 1 + 1 ) ) = ( 2 + 2 )
53		2p2e4 10727	. . . . . . . . . . . . . 14 |- ( 2 + 2 ) = 4
54	52, 53	eqtri 2473	. . . . . . . . . . . . 13 |- ( ( 1 x. 2 ) + ( 1 + 1 ) ) = 4
55		8p1e9 10740	. . . . . . . . . . . . . 14 |- ( 8 + 1 ) = 9
56		9t2e18 11146	. . . . . . . . . . . . . 14 |- ( 9 x. 2 ) = ; 1 8
57	2, 3, 55, 56	decsuc 11074	. . . . . . . . . . . . 13 |- ( ( 9 x. 2 ) + 1 ) = ; 1 9
58	2, 37, 2, 2, 48, 49, 13, 37, 2, 54, 57	decmac 11090	. . . . . . . . . . . 12 |- ( (; 1 9 x. 2 ) + ; 1 1 ) = ; 4 9
59		1lt9 10811	. . . . . . . . . . . . 13 |- 1 < 9
60	2, 2, 44, 59	declt 11072	. . . . . . . . . . . 12 |- ; 1 1 < ; 1 9
61	45, 13, 47, 58, 60	ndvdsi 14391	. . . . . . . . . . 11 |- -. ; 1 9 || ; 4 9
62		19prm 15089	. . . . . . . . . . . 12 |- ; 1 9 e. Prime
63		coprm 14657	. . . . . . . . . . . 12 |- ( (; 1 9 e. Prime /\ ; 4 9 e. ZZ ) -> ( -. ; 1 9 || ; 4 9 <-> (; 1 9 gcd ; 4 9 ) = 1 ) )
64	62, 40, 63	mp2an 678	. . . . . . . . . . 11 |- ( -. ; 1 9 || ; 4 9 <-> (; 1 9 gcd ; 4 9 ) = 1 )
65	61, 64	mpbi 212	. . . . . . . . . 10 |- (; 1 9 gcd ; 4 9 ) = 1
66	43, 65	eqtri 2473	. . . . . . . . 9 |- (; 4 9 gcd ; 1 9 ) = 1
67		eqid 2451	. . . . . . . . . 10 |- ; 4 9 = ; 4 9
68		4cn 10687	. . . . . . . . . . . . 13 |- 4 e. CC
69	68	mulid2i 9646	. . . . . . . . . . . 12 |- ( 1 x. 4 ) = 4
70	69, 22	oveq12i 6302	. . . . . . . . . . 11 |- ( ( 1 x. 4 ) + ( 1 + 1 ) ) = ( 4 + 2 )
71		4p2e6 10744	. . . . . . . . . . 11 |- ( 4 + 2 ) = 6
72	70, 71	eqtri 2473	. . . . . . . . . 10 |- ( ( 1 x. 4 ) + ( 1 + 1 ) ) = 6
73		9cn 10697	. . . . . . . . . . . . 13 |- 9 e. CC
74	73	mulid2i 9646	. . . . . . . . . . . 12 |- ( 1 x. 9 ) = 9
75	74	oveq1i 6300	. . . . . . . . . . 11 |- ( ( 1 x. 9 ) + 9 ) = ( 9 + 9 )
76		9p9e18 11120	. . . . . . . . . . 11 |- ( 9 + 9 ) = ; 1 8
77	75, 76	eqtri 2473	. . . . . . . . . 10 |- ( ( 1 x. 9 ) + 9 ) = ; 1 8
78	30, 37, 2, 37, 67, 48, 2, 3, 2, 72, 77	decma2c 11091	. . . . . . . . 9 |- ( ( 1 x. ; 4 9 ) + ; 1 9 ) = ; 6 8
79	2, 39, 38, 66, 78	gcdi 15045	. . . . . . . 8 |- (; 6 8 gcd ; 4 9 ) = 1
80		eqid 2451	. . . . . . . . 9 |- ; 6 8 = ; 6 8
81		6cn 10691	. . . . . . . . . . . 12 |- 6 e. CC
82	81	mulid2i 9646	. . . . . . . . . . 11 |- ( 1 x. 6 ) = 6
83		4p1e5 10736	. . . . . . . . . . 11 |- ( 4 + 1 ) = 5
84	82, 83	oveq12i 6302	. . . . . . . . . 10 |- ( ( 1 x. 6 ) + ( 4 + 1 ) ) = ( 6 + 5 )
85		6p5e11 11101	. . . . . . . . . 10 |- ( 6 + 5 ) = ; 1 1
86	84, 85	eqtri 2473	. . . . . . . . 9 |- ( ( 1 x. 6 ) + ( 4 + 1 ) ) = ; 1 1
87		8cn 10695	. . . . . . . . . . . 12 |- 8 e. CC
88	87	mulid2i 9646	. . . . . . . . . . 11 |- ( 1 x. 8 ) = 8
89	88	oveq1i 6300	. . . . . . . . . 10 |- ( ( 1 x. 8 ) + 9 ) = ( 8 + 9 )
90		9p8e17 11119	. . . . . . . . . . 11 |- ( 9 + 8 ) = ; 1 7
91	73, 87, 90	addcomli 9825	. . . . . . . . . 10 |- ( 8 + 9 ) = ; 1 7
92	89, 91	eqtri 2473	. . . . . . . . 9 |- ( ( 1 x. 8 ) + 9 ) = ; 1 7
93	26, 3, 30, 37, 80, 67, 2, 27, 2, 86, 92	decma2c 11091	. . . . . . . 8 |- ( ( 1 x. ; 6 8 ) + ; 4 9 ) = ;; 1 1 7
94	2, 38, 36, 79, 93	gcdi 15045	. . . . . . 7 |- (;; 1 1 7 gcd ; 6 8 ) = 1
95		eqid 2451	. . . . . . . 8 |- ;; 1 1 7 = ;; 1 1 7
96		6p1e7 10738	. . . . . . . . . 10 |- ( 6 + 1 ) = 7
97	27	dec0h 11067	. . . . . . . . . 10 |- 7 = ; 0 7
98	96, 97	eqtri 2473	. . . . . . . . 9 |- ( 6 + 1 ) = ; 0 7
99		ax-1cn 9597	. . . . . . . . . . . 12 |- 1 e. CC
100	99	mulid1i 9645	. . . . . . . . . . 11 |- ( 1 x. 1 ) = 1
101		00id 9808	. . . . . . . . . . 11 |- ( 0 + 0 ) = 0
102	100, 101	oveq12i 6302	. . . . . . . . . 10 |- ( ( 1 x. 1 ) + ( 0 + 0 ) ) = ( 1 + 0 )
103	99	addid1i 9820	. . . . . . . . . 10 |- ( 1 + 0 ) = 1
104	102, 103	eqtri 2473	. . . . . . . . 9 |- ( ( 1 x. 1 ) + ( 0 + 0 ) ) = 1
105	100	oveq1i 6300	. . . . . . . . . 10 |- ( ( 1 x. 1 ) + 7 ) = ( 1 + 7 )
106		7cn 10693	. . . . . . . . . . 11 |- 7 e. CC
107		7p1e8 10739	. . . . . . . . . . 11 |- ( 7 + 1 ) = 8
108	106, 99, 107	addcomli 9825	. . . . . . . . . 10 |- ( 1 + 7 ) = 8
109	3	dec0h 11067	. . . . . . . . . 10 |- 8 = ; 0 8
110	105, 108, 109	3eqtri 2477	. . . . . . . . 9 |- ( ( 1 x. 1 ) + 7 ) = ; 0 8
111	2, 2, 16, 27, 49, 98, 2, 3, 16, 104, 110	decma2c 11091	. . . . . . . 8 |- ( ( 1 x. ; 1 1 ) + ( 6 + 1 ) ) = ; 1 8
112	106	mulid2i 9646	. . . . . . . . . 10 |- ( 1 x. 7 ) = 7
113	112	oveq1i 6300	. . . . . . . . 9 |- ( ( 1 x. 7 ) + 8 ) = ( 7 + 8 )
114		8p7e15 11111	. . . . . . . . . 10 |- ( 8 + 7 ) = ; 1 5
115	87, 106, 114	addcomli 9825	. . . . . . . . 9 |- ( 7 + 8 ) = ; 1 5
116	113, 115	eqtri 2473	. . . . . . . 8 |- ( ( 1 x. 7 ) + 8 ) = ; 1 5
117	34, 27, 26, 3, 95, 80, 2, 14, 2, 111, 116	decma2c 11091	. . . . . . 7 |- ( ( 1 x. ;; 1 1 7 ) + ; 6 8 ) = ;; 1 8 5
118	2, 36, 35, 94, 117	gcdi 15045	. . . . . 6 |- (;; 1 8 5 gcd ;; 1 1 7 ) = 1
119		eqid 2451	. . . . . . 7 |- ;; 1 8 5 = ;; 1 8 5
120		eqid 2451	. . . . . . . 8 |- ; 1 8 = ; 1 8
121	2, 2, 22, 49	decsuc 11074	. . . . . . . 8 |- (; 1 1 + 1 ) = ; 1 2
122	50	mulid1i 9645	. . . . . . . . . 10 |- ( 2 x. 1 ) = 2
123	122, 22	oveq12i 6302	. . . . . . . . 9 |- ( ( 2 x. 1 ) + ( 1 + 1 ) ) = ( 2 + 2 )
124	123, 53	eqtri 2473	. . . . . . . 8 |- ( ( 2 x. 1 ) + ( 1 + 1 ) ) = 4
125		8t2e16 11139	. . . . . . . . . 10 |- ( 8 x. 2 ) = ; 1 6
126	87, 50, 125	mulcomli 9650	. . . . . . . . 9 |- ( 2 x. 8 ) = ; 1 6
127		6p2e8 10751	. . . . . . . . 9 |- ( 6 + 2 ) = 8
128	2, 26, 13, 126, 127	decaddi 11095	. . . . . . . 8 |- ( ( 2 x. 8 ) + 2 ) = ; 1 8
129	2, 3, 2, 13, 120, 121, 13, 3, 2, 124, 128	decma2c 11091	. . . . . . 7 |- ( ( 2 x. ; 1 8 ) + (; 1 1 + 1 ) ) = ; 4 8
130		5cn 10689	. . . . . . . . . 10 |- 5 e. CC
131		5t2e10 10764	. . . . . . . . . 10 |- ( 5 x. 2 ) = 10
132	130, 50, 131	mulcomli 9650	. . . . . . . . 9 |- ( 2 x. 5 ) = 10
133		dec10 11081	. . . . . . . . 9 |- 10 = ; 1 0
134	132, 133	eqtri 2473	. . . . . . . 8 |- ( 2 x. 5 ) = ; 1 0
135	106	addid2i 9821	. . . . . . . 8 |- ( 0 + 7 ) = 7
136	2, 16, 27, 134, 135	decaddi 11095	. . . . . . 7 |- ( ( 2 x. 5 ) + 7 ) = ; 1 7
137	4, 14, 34, 27, 119, 95, 13, 27, 2, 129, 136	decma2c 11091	. . . . . 6 |- ( ( 2 x. ;; 1 8 5 ) + ;; 1 1 7 ) = ;; 4 8 7
138	13, 35, 33, 118, 137	gcdi 15045	. . . . 5 |- (;; 4 8 7 gcd ;; 1 8 5 ) = 1
139		eqid 2451	. . . . . 6 |- ;; 4 8 7 = ;; 4 8 7
140		eqid 2451	. . . . . . 7 |- ; 4 8 = ; 4 8
141	2, 3, 55, 120	decsuc 11074	. . . . . . 7 |- (; 1 8 + 1 ) = ; 1 9
142	30, 3, 2, 37, 140, 141, 2, 27, 2, 72, 92	decma2c 11091	. . . . . 6 |- ( ( 1 x. ; 4 8 ) + (; 1 8 + 1 ) ) = ; 6 7
143	112	oveq1i 6300	. . . . . . 7 |- ( ( 1 x. 7 ) + 5 ) = ( 7 + 5 )
144		7p5e12 11104	. . . . . . 7 |- ( 7 + 5 ) = ; 1 2
145	143, 144	eqtri 2473	. . . . . 6 |- ( ( 1 x. 7 ) + 5 ) = ; 1 2
146	31, 27, 4, 14, 139, 119, 2, 13, 2, 142, 145	decma2c 11091	. . . . 5 |- ( ( 1 x. ;; 4 8 7 ) + ;; 1 8 5 ) = ;; 6 7 2
147	2, 33, 32, 138, 146	gcdi 15045	. . . 4 |- (;; 6 7 2 gcd ;; 4 8 7 ) = 1
148		eqid 2451	. . . . 5 |- ;; 6 7 2 = ;; 6 7 2
149		eqid 2451	. . . . . 6 |- ; 6 7 = ; 6 7
150	30, 3, 55, 140	decsuc 11074	. . . . . 6 |- (; 4 8 + 1 ) = ; 4 9
151	71	oveq2i 6301	. . . . . . 7 |- ( ( 2 x. 6 ) + ( 4 + 2 ) ) = ( ( 2 x. 6 ) + 6 )
152		6t2e12 11128	. . . . . . . . 9 |- ( 6 x. 2 ) = ; 1 2
153	81, 50, 152	mulcomli 9650	. . . . . . . 8 |- ( 2 x. 6 ) = ; 1 2
154	81, 50, 127	addcomli 9825	. . . . . . . 8 |- ( 2 + 6 ) = 8
155	2, 13, 26, 153, 154	decaddi 11095	. . . . . . 7 |- ( ( 2 x. 6 ) + 6 ) = ; 1 8
156	151, 155	eqtri 2473	. . . . . 6 |- ( ( 2 x. 6 ) + ( 4 + 2 ) ) = ; 1 8
157		7t2e14 11133	. . . . . . . 8 |- ( 7 x. 2 ) = ; 1 4
158	106, 50, 157	mulcomli 9650	. . . . . . 7 |- ( 2 x. 7 ) = ; 1 4
159		9p4e13 11115	. . . . . . . 8 |- ( 9 + 4 ) = ; 1 3
160	73, 68, 159	addcomli 9825	. . . . . . 7 |- ( 4 + 9 ) = ; 1 3
161	2, 30, 37, 158, 22, 9, 160	decaddci 11096	. . . . . 6 |- ( ( 2 x. 7 ) + 9 ) = ; 2 3
162	26, 27, 30, 37, 149, 150, 13, 9, 13, 156, 161	decma2c 11091	. . . . 5 |- ( ( 2 x. ; 6 7 ) + (; 4 8 + 1 ) ) = ;; 1 8 3
163		2t2e4 10759	. . . . . . 7 |- ( 2 x. 2 ) = 4
164	163	oveq1i 6300	. . . . . 6 |- ( ( 2 x. 2 ) + 7 ) = ( 4 + 7 )
165		7p4e11 11103	. . . . . . 7 |- ( 7 + 4 ) = ; 1 1
166	106, 68, 165	addcomli 9825	. . . . . 6 |- ( 4 + 7 ) = ; 1 1
167	164, 166	eqtri 2473	. . . . 5 |- ( ( 2 x. 2 ) + 7 ) = ; 1 1
168	28, 13, 31, 27, 148, 139, 13, 2, 2, 162, 167	decma2c 11091	. . . 4 |- ( ( 2 x. ;; 6 7 2 ) + ;; 4 8 7 ) = ;;; 1 8 3 1
169	13, 32, 29, 147, 168	gcdi 15045	. . 3 |- (;;; 1 8 3 1 gcd ;; 6 7 2 ) = 1
170		eqid 2451	. . . . . 6 |- ;; 1 8 3 = ;; 1 8 3
171	28	nn0cni 10881	. . . . . . 7 |- ; 6 7 e. CC
172	171	addid1i 9820	. . . . . 6 |- (; 6 7 + 0 ) = ; 6 7
173	99	addid2i 9821	. . . . . . . . 9 |- ( 0 + 1 ) = 1
174	100, 173	oveq12i 6302	. . . . . . . 8 |- ( ( 1 x. 1 ) + ( 0 + 1 ) ) = ( 1 + 1 )
175	174, 22	eqtri 2473	. . . . . . 7 |- ( ( 1 x. 1 ) + ( 0 + 1 ) ) = 2
176	88	oveq1i 6300	. . . . . . . 8 |- ( ( 1 x. 8 ) + 7 ) = ( 8 + 7 )
177	176, 114	eqtri 2473	. . . . . . 7 |- ( ( 1 x. 8 ) + 7 ) = ; 1 5
178	2, 3, 16, 27, 120, 98, 2, 14, 2, 175, 177	decma2c 11091	. . . . . 6 |- ( ( 1 x. ; 1 8 ) + ( 6 + 1 ) ) = ; 2 5
179		3cn 10684	. . . . . . . . 9 |- 3 e. CC
180	179	mulid2i 9646	. . . . . . . 8 |- ( 1 x. 3 ) = 3
181	180	oveq1i 6300	. . . . . . 7 |- ( ( 1 x. 3 ) + 7 ) = ( 3 + 7 )
182		7p3e10 10755	. . . . . . . 8 |- ( 7 + 3 ) = 10
183	106, 179, 182	addcomli 9825	. . . . . . 7 |- ( 3 + 7 ) = 10
184	181, 183, 133	3eqtri 2477	. . . . . 6 |- ( ( 1 x. 3 ) + 7 ) = ; 1 0
185	4, 9, 26, 27, 170, 172, 2, 16, 2, 178, 184	decma2c 11091	. . . . 5 |- ( ( 1 x. ;; 1 8 3 ) + (; 6 7 + 0 ) ) = ;; 2 5 0
186	100	oveq1i 6300	. . . . . 6 |- ( ( 1 x. 1 ) + 2 ) = ( 1 + 2 )
187		1p2e3 10734	. . . . . 6 |- ( 1 + 2 ) = 3
188	9	dec0h 11067	. . . . . 6 |- 3 = ; 0 3
189	186, 187, 188	3eqtri 2477	. . . . 5 |- ( ( 1 x. 1 ) + 2 ) = ; 0 3
190	10, 2, 28, 13, 23, 148, 2, 9, 16, 185, 189	decma2c 11091	. . . 4 |- ( ( 1 x. ;;; 1 8 3 1 ) + ;; 6 7 2 ) = ;;; 2 5 0 3
191	190, 12	eqtr4i 2476	. . 3 |- ( ( 1 x. ;;; 1 8 3 1 ) + ;; 6 7 2 ) = N
192	2, 29, 11, 169, 191	gcdi 15045	. 2 |- ( N gcd ;;; 1 8 3 1 ) = 1
193	8, 11, 20, 25, 192	gcdmodi 15046	1 |- ( ( ( 2 ^; 1 8 ) - 1 ) gcd N ) = 1

Syntax hints:   -. wn 3   <-> wb 188   = wceq 1444   e. wcel 1887   class class class wbr 4402  (class class class)co 6290   0cc0 9539   1c1 9540   + caddc 9542   x. cmul 9544   - cmin 9860   NNcn 10609   2c2 10659   3c3 10660   4c4 10661   5c5 10662   6c6 10663   7c7 10664   8c8 10665   9c9 10666   10c10 10667   NN0cn0 10869   ZZcz 10937  ;cdc 11051   ^cexp 12272   || cdvds 14305   gcd cgcd 14468   Primecprime 14622

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1669  ax-4 1682  ax-5 1758  ax-6 1805  ax-7 1851  ax-8 1889  ax-9 1896  ax-10 1915  ax-11 1920  ax-12 1933  ax-13 2091  ax-ext 2431  ax-sep 4525  ax-nul 4534  ax-pow 4581  ax-pr 4639  ax-un 6583  ax-cnex 9595  ax-resscn 9596  ax-1cn 9597  ax-icn 9598  ax-addcl 9599  ax-addrcl 9600  ax-mulcl 9601  ax-mulrcl 9602  ax-mulcom 9603  ax-addass 9604  ax-mulass 9605  ax-distr 9606  ax-i2m1 9607  ax-1ne0 9608  ax-1rid 9609  ax-rnegex 9610  ax-rrecex 9611  ax-cnre 9612  ax-pre-lttri 9613  ax-pre-lttrn 9614  ax-pre-ltadd 9615  ax-pre-mulgt0 9616  ax-pre-sup 9617

This theorem depends on definitions:  df-bi 189  df-or 372  df-an 373  df-3or 986  df-3an 987  df-tru 1447  df-ex 1664  df-nf 1668  df-sb 1798  df-eu 2303  df-mo 2304  df-clab 2438  df-cleq 2444  df-clel 2447  df-nfc 2581  df-ne 2624  df-nel 2625  df-ral 2742  df-rex 2743  df-reu 2744  df-rmo 2745  df-rab 2746  df-v 3047  df-sbc 3268  df-csb 3364  df-dif 3407  df-un 3409  df-in 3411  df-ss 3418  df-pss 3420  df-nul 3732  df-if 3882  df-pw 3953  df-sn 3969  df-pr 3971  df-tp 3973  df-op 3975  df-uni 4199  df-int 4235  df-iun 4280  df-br 4403  df-opab 4462  df-mpt 4463  df-tr 4498  df-eprel 4745  df-id 4749  df-po 4755  df-so 4756  df-fr 4793  df-we 4795  df-xp 4840  df-rel 4841  df-cnv 4842  df-co 4843  df-dm 4844  df-rn 4845  df-res 4846  df-ima 4847  df-pred 5380  df-ord 5426  df-on 5427  df-lim 5428  df-suc 5429  df-iota 5546  df-fun 5584  df-fn 5585  df-f 5586  df-f1 5587  df-fo 5588  df-f1o 5589  df-fv 5590  df-riota 6252  df-ov 6293  df-oprab 6294  df-mpt2 6295  df-om 6693  df-1st 6793  df-2nd 6794  df-wrecs 7028  df-recs 7090  df-rdg 7128  df-1o 7182  df-2o 7183  df-oadd 7186  df-er 7363  df-en 7570  df-dom 7571  df-sdom 7572  df-fin 7573  df-sup 7956  df-inf 7957  df-pnf 9677  df-mnf 9678  df-xr 9679  df-ltxr 9680  df-le 9681  df-sub 9862  df-neg 9863  df-div 10270  df-nn 10610  df-2 10668  df-3 10669  df-4 10670  df-5 10671  df-6 10672  df-7 10673  df-8 10674  df-9 10675  df-10 10676  df-n0 10870  df-z 10938  df-dec 11052  df-uz 11160  df-rp 11303  df-fz 11785  df-fl 12028  df-mod 12097  df-seq 12214  df-exp 12273  df-cj 13162  df-re 13163  df-im 13164  df-sqrt 13298  df-abs 13299  df-dvds 14306  df-gcd 14469  df-prm 14623

This theorem is referenced by:  2503prm  15111