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

Theorem 1259lem4 16072
Description: Lemma for 1259prm 16074. Calculate a power mod. In decimal, we calculate 2↑306 = (2↑76)↑4 · 4≡5↑4 · 4 = 2𝑁 − 18, 2↑612 = (2↑306)↑2≡18↑2 = 324, 2↑629 = 2↑612 · 2↑17≡324 · 136 = 35𝑁 − 1 and finally 2↑(𝑁 − 1) = (2↑629)↑2≡1↑2 = 1. (Contributed by Mario Carneiro, 22-Feb-2014.) (Revised by Mario Carneiro, 20-Apr-2015.) (Proof shortened by AV, 16-Sep-2021.)
Hypothesis
Ref Expression
1259prm.1 𝑁 = 1259
Assertion
Ref Expression
1259lem4 ((2↑(𝑁 − 1)) mod 𝑁) = (1 mod 𝑁)

Proof of Theorem 1259lem4
StepHypRef Expression
1 2nn 11386 . 2 2 ∈ ℕ
2 6nn0 11600 . . . 4 6 ∈ ℕ0
3 2nn0 11596 . . . 4 2 ∈ ℕ0
42, 3deccl 11794 . . 3 62 ∈ ℕ0
5 9nn0 11603 . . 3 9 ∈ ℕ0
64, 5deccl 11794 . 2 629 ∈ ℕ0
7 0z 11674 . 2 0 ∈ ℤ
8 1nn 11328 . 2 1 ∈ ℕ
9 1nn0 11595 . 2 1 ∈ ℕ0
109, 3deccl 11794 . . . . . . 7 12 ∈ ℕ0
11 5nn0 11599 . . . . . . 7 5 ∈ ℕ0
1210, 11deccl 11794 . . . . . 6 125 ∈ ℕ0
13 8nn0 11602 . . . . . 6 8 ∈ ℕ0
1412, 13deccl 11794 . . . . 5 1258 ∈ ℕ0
1514nn0cni 11591 . . . 4 1258 ∈ ℂ
16 ax-1cn 10289 . . . 4 1 ∈ ℂ
17 1259prm.1 . . . . 5 𝑁 = 1259
18 8p1e9 11469 . . . . . 6 (8 + 1) = 9
19 eqid 2817 . . . . . 6 1258 = 1258
2012, 13, 18, 19decsuc 11810 . . . . 5 (1258 + 1) = 1259
2117, 20eqtr4i 2842 . . . 4 𝑁 = (1258 + 1)
2215, 16, 21mvrraddi 10593 . . 3 (𝑁 − 1) = 1258
2322, 14eqeltri 2892 . 2 (𝑁 − 1) ∈ ℕ0
24 9nn 11417 . . . . 5 9 ∈ ℕ
2512, 24decnncl 11799 . . . 4 1259 ∈ ℕ
2617, 25eqeltri 2892 . . 3 𝑁 ∈ ℕ
272, 9deccl 11794 . . . 4 61 ∈ ℕ0
2827, 3deccl 11794 . . 3 612 ∈ ℕ0
29 3nn0 11597 . . . . 5 3 ∈ ℕ0
30 4nn0 11598 . . . . 5 4 ∈ ℕ0
3129, 30deccl 11794 . . . 4 34 ∈ ℕ0
3231nn0zi 11688 . . 3 34 ∈ ℤ
3329, 3deccl 11794 . . . 4 32 ∈ ℕ0
3433, 30deccl 11794 . . 3 324 ∈ ℕ0
35 7nn0 11601 . . . 4 7 ∈ ℕ0
369, 35deccl 11794 . . 3 17 ∈ ℕ0
379, 29deccl 11794 . . . 4 13 ∈ ℕ0
3837, 2deccl 11794 . . 3 136 ∈ ℕ0
39 0nn0 11594 . . . . . 6 0 ∈ ℕ0
4029, 39deccl 11794 . . . . 5 30 ∈ ℕ0
4140, 2deccl 11794 . . . 4 306 ∈ ℕ0
42 8nn 11413 . . . . 5 8 ∈ ℕ
439, 42decnncl 11799 . . . 4 18 ∈ ℕ
4410, 30deccl 11794 . . . . 5 124 ∈ ℕ0
4544, 9deccl 11794 . . . 4 1241 ∈ ℕ0
469, 11deccl 11794 . . . . . 6 15 ∈ ℕ0
4746, 29deccl 11794 . . . . 5 153 ∈ ℕ0
48 1z 11693 . . . . 5 1 ∈ ℤ
4911, 39deccl 11794 . . . . 5 50 ∈ ℕ0
5046, 3deccl 11794 . . . . . 6 152 ∈ ℕ0
513, 11deccl 11794 . . . . . 6 25 ∈ ℕ0
5235, 2deccl 11794 . . . . . . 7 76 ∈ ℕ0
53171259lem3 16071 . . . . . . 7 ((2↑76) mod 𝑁) = (5 mod 𝑁)
54 eqid 2817 . . . . . . . 8 76 = 76
55 4p1e5 11465 . . . . . . . . 9 (4 + 1) = 5
56 7cn 11411 . . . . . . . . . 10 7 ∈ ℂ
57 2cn 11388 . . . . . . . . . 10 2 ∈ ℂ
58 7t2e14 11888 . . . . . . . . . 10 (7 · 2) = 14
5956, 57, 58mulcomli 10344 . . . . . . . . 9 (2 · 7) = 14
609, 30, 55, 59decsuc 11810 . . . . . . . 8 ((2 · 7) + 1) = 15
61 6cn 11407 . . . . . . . . 9 6 ∈ ℂ
62 6t2e12 11883 . . . . . . . . 9 (6 · 2) = 12
6361, 57, 62mulcomli 10344 . . . . . . . 8 (2 · 6) = 12
643, 35, 2, 54, 3, 9, 60, 63decmul2c 11845 . . . . . . 7 (2 · 76) = 152
6551nn0cni 11591 . . . . . . . . 9 25 ∈ ℂ
6665addid2i 10519 . . . . . . . 8 (0 + 25) = 25
6726nncni 11326 . . . . . . . . . 10 𝑁 ∈ ℂ
6867mul02i 10520 . . . . . . . . 9 (0 · 𝑁) = 0
6968oveq1i 6894 . . . . . . . 8 ((0 · 𝑁) + 25) = (0 + 25)
70 5t5e25 11882 . . . . . . . 8 (5 · 5) = 25
7166, 69, 703eqtr4i 2849 . . . . . . 7 ((0 · 𝑁) + 25) = (5 · 5)
7226, 1, 52, 7, 11, 51, 53, 64, 71mod2xi 16010 . . . . . 6 ((2↑152) mod 𝑁) = (25 mod 𝑁)
73 2p1e3 11462 . . . . . . 7 (2 + 1) = 3
74 eqid 2817 . . . . . . 7 152 = 152
7546, 3, 73, 74decsuc 11810 . . . . . 6 (152 + 1) = 153
7649nn0cni 11591 . . . . . . . 8 50 ∈ ℂ
7776addid2i 10519 . . . . . . 7 (0 + 50) = 50
7868oveq1i 6894 . . . . . . 7 ((0 · 𝑁) + 50) = (0 + 50)
79 eqid 2817 . . . . . . . 8 25 = 25
80 2t2e4 11483 . . . . . . . . . 10 (2 · 2) = 4
8180oveq1i 6894 . . . . . . . . 9 ((2 · 2) + 1) = (4 + 1)
8281, 55eqtri 2839 . . . . . . . 8 ((2 · 2) + 1) = 5
83 5t2e10 11879 . . . . . . . 8 (5 · 2) = 10
843, 3, 11, 79, 39, 9, 82, 83decmul1c 11844 . . . . . . 7 (25 · 2) = 50
8577, 78, 843eqtr4i 2849 . . . . . 6 ((0 · 𝑁) + 50) = (25 · 2)
8626, 1, 50, 7, 51, 49, 72, 75, 85modxp1i 16011 . . . . 5 ((2↑153) mod 𝑁) = (50 mod 𝑁)
87 eqid 2817 . . . . . 6 153 = 153
88 eqid 2817 . . . . . . . . 9 15 = 15
8957mulid1i 10339 . . . . . . . . . . 11 (2 · 1) = 2
9089oveq1i 6894 . . . . . . . . . 10 ((2 · 1) + 1) = (2 + 1)
9190, 73eqtri 2839 . . . . . . . . 9 ((2 · 1) + 1) = 3
92 5cn 11403 . . . . . . . . . 10 5 ∈ ℂ
9392, 57, 83mulcomli 10344 . . . . . . . . 9 (2 · 5) = 10
943, 9, 11, 88, 39, 9, 91, 93decmul2c 11845 . . . . . . . 8 (2 · 15) = 30
9594oveq1i 6894 . . . . . . 7 ((2 · 15) + 0) = (30 + 0)
9640nn0cni 11591 . . . . . . . 8 30 ∈ ℂ
9796addid1i 10518 . . . . . . 7 (30 + 0) = 30
9895, 97eqtri 2839 . . . . . 6 ((2 · 15) + 0) = 30
99 3cn 11394 . . . . . . . 8 3 ∈ ℂ
100 3t2e6 11485 . . . . . . . 8 (3 · 2) = 6
10199, 57, 100mulcomli 10344 . . . . . . 7 (2 · 3) = 6
1022dec0h 11801 . . . . . . 7 6 = 06
103101, 102eqtri 2839 . . . . . 6 (2 · 3) = 06
1043, 46, 29, 87, 2, 39, 98, 103decmul2c 11845 . . . . 5 (2 · 153) = 306
10567mulid2i 10340 . . . . . . . 8 (1 · 𝑁) = 𝑁
106105, 17eqtri 2839 . . . . . . 7 (1 · 𝑁) = 1259
107 eqid 2817 . . . . . . 7 1241 = 1241
1083, 30deccl 11794 . . . . . . . 8 24 ∈ ℕ0
109 eqid 2817 . . . . . . . . 9 24 = 24
1103, 30, 55, 109decsuc 11810 . . . . . . . 8 (24 + 1) = 25
111 eqid 2817 . . . . . . . . 9 125 = 125
112 eqid 2817 . . . . . . . . 9 124 = 124
113 eqid 2817 . . . . . . . . . 10 12 = 12
114 1p1e2 11445 . . . . . . . . . 10 (1 + 1) = 2
115 2p2e4 11455 . . . . . . . . . 10 (2 + 2) = 4
1169, 3, 9, 3, 113, 113, 114, 115decadd 11833 . . . . . . . . 9 (12 + 12) = 24
117 5p4e9 11477 . . . . . . . . 9 (5 + 4) = 9
11810, 11, 10, 30, 111, 112, 116, 117decadd 11833 . . . . . . . 8 (125 + 124) = 249
119108, 110, 118decsucc 11820 . . . . . . 7 ((125 + 124) + 1) = 250
120 9p1e10 11781 . . . . . . 7 (9 + 1) = 10
12112, 5, 44, 9, 106, 107, 119, 120decaddc2 11835 . . . . . 6 ((1 · 𝑁) + 1241) = 2500
122 eqid 2817 . . . . . . 7 50 = 50
12392mul02i 10520 . . . . . . . . . 10 (0 · 5) = 0
12411, 11, 39, 122, 39, 70, 123decmul1 11843 . . . . . . . . 9 (50 · 5) = 250
125124oveq1i 6894 . . . . . . . 8 ((50 · 5) + 0) = (250 + 0)
12651, 39deccl 11794 . . . . . . . . . 10 250 ∈ ℕ0
127126nn0cni 11591 . . . . . . . . 9 250 ∈ ℂ
128127addid1i 10518 . . . . . . . 8 (250 + 0) = 250
129125, 128eqtri 2839 . . . . . . 7 ((50 · 5) + 0) = 250
13076mul01i 10521 . . . . . . . 8 (50 · 0) = 0
13139dec0h 11801 . . . . . . . 8 0 = 00
132130, 131eqtri 2839 . . . . . . 7 (50 · 0) = 00
13349, 11, 39, 122, 39, 39, 129, 132decmul2c 11845 . . . . . 6 (50 · 50) = 2500
134121, 133eqtr4i 2842 . . . . 5 ((1 · 𝑁) + 1241) = (50 · 50)
13526, 1, 47, 48, 49, 45, 86, 104, 134mod2xi 16010 . . . 4 ((2↑306) mod 𝑁) = (1241 mod 𝑁)
136 eqid 2817 . . . . 5 306 = 306
137 eqid 2817 . . . . . 6 30 = 30
1389dec0h 11801 . . . . . 6 1 = 01
139 00id 10506 . . . . . . . 8 (0 + 0) = 0
140101, 139oveq12i 6896 . . . . . . 7 ((2 · 3) + (0 + 0)) = (6 + 0)
14161addid1i 10518 . . . . . . 7 (6 + 0) = 6
142140, 141eqtri 2839 . . . . . 6 ((2 · 3) + (0 + 0)) = 6
14357mul01i 10521 . . . . . . . 8 (2 · 0) = 0
144143oveq1i 6894 . . . . . . 7 ((2 · 0) + 1) = (0 + 1)
145 0p1e1 11442 . . . . . . 7 (0 + 1) = 1
146144, 145, 1383eqtri 2843 . . . . . 6 ((2 · 0) + 1) = 01
14729, 39, 39, 9, 137, 138, 3, 9, 39, 142, 146decma2c 11832 . . . . 5 ((2 · 30) + 1) = 61
1483, 40, 2, 136, 3, 9, 147, 63decmul2c 11845 . . . 4 (2 · 306) = 612
149 eqid 2817 . . . . . 6 18 = 18
15010, 30, 55, 112decsuc 11810 . . . . . 6 (124 + 1) = 125
151 8cn 11415 . . . . . . 7 8 ∈ ℂ
152151, 16, 18addcomli 10523 . . . . . 6 (1 + 8) = 9
15344, 9, 9, 13, 107, 149, 150, 152decadd 11833 . . . . 5 (1241 + 18) = 1259
154153, 17eqtr4i 2842 . . . 4 (1241 + 18) = 𝑁
15534nn0cni 11591 . . . . . 6 324 ∈ ℂ
156155addid2i 10519 . . . . 5 (0 + 324) = 324
15768oveq1i 6894 . . . . 5 ((0 · 𝑁) + 324) = (0 + 324)
1589, 13deccl 11794 . . . . . 6 18 ∈ ℕ0
1599, 30deccl 11794 . . . . . 6 14 ∈ ℕ0
160 eqid 2817 . . . . . . 7 14 = 14
16116mulid1i 10339 . . . . . . . . 9 (1 · 1) = 1
162161, 114oveq12i 6896 . . . . . . . 8 ((1 · 1) + (1 + 1)) = (1 + 2)
163 1p2e3 11463 . . . . . . . 8 (1 + 2) = 3
164162, 163eqtri 2839 . . . . . . 7 ((1 · 1) + (1 + 1)) = 3
165151mulid1i 10339 . . . . . . . . 9 (8 · 1) = 8
166165oveq1i 6894 . . . . . . . 8 ((8 · 1) + 4) = (8 + 4)
167 8p4e12 11861 . . . . . . . 8 (8 + 4) = 12
168166, 167eqtri 2839 . . . . . . 7 ((8 · 1) + 4) = 12
1699, 13, 9, 30, 149, 160, 9, 3, 9, 164, 168decmac 11831 . . . . . 6 ((18 · 1) + 14) = 32
170151mulid2i 10340 . . . . . . . . 9 (1 · 8) = 8
171170oveq1i 6894 . . . . . . . 8 ((1 · 8) + 6) = (8 + 6)
172 8p6e14 11863 . . . . . . . 8 (8 + 6) = 14
173171, 172eqtri 2839 . . . . . . 7 ((1 · 8) + 6) = 14
174 8t8e64 11900 . . . . . . 7 (8 · 8) = 64
17513, 9, 13, 149, 30, 2, 173, 174decmul1c 11844 . . . . . 6 (18 · 8) = 144
176158, 9, 13, 149, 30, 159, 169, 175decmul2c 11845 . . . . 5 (18 · 18) = 324
177156, 157, 1763eqtr4i 2849 . . . 4 ((0 · 𝑁) + 324) = (18 · 18)
1781, 41, 7, 43, 34, 45, 135, 148, 154, 177mod2xnegi 16012 . . 3 ((2↑612) mod 𝑁) = (324 mod 𝑁)
179171259lem1 16069 . . 3 ((2↑17) mod 𝑁) = (136 mod 𝑁)
180 eqid 2817 . . . 4 612 = 612
181 eqid 2817 . . . 4 17 = 17
182 eqid 2817 . . . . 5 61 = 61
1832, 9, 114, 182decsuc 11810 . . . 4 (61 + 1) = 62
184 7p2e9 11480 . . . . 5 (7 + 2) = 9
18556, 57, 184addcomli 10523 . . . 4 (2 + 7) = 9
18627, 3, 9, 35, 180, 181, 183, 185decadd 11833 . . 3 (612 + 17) = 629
18729, 9deccl 11794 . . . . 5 31 ∈ ℕ0
188 eqid 2817 . . . . . . 7 31 = 31
189 3p2e5 11470 . . . . . . . . 9 (3 + 2) = 5
19099, 57, 189addcomli 10523 . . . . . . . 8 (2 + 3) = 5
1919, 3, 29, 113, 190decaddi 11839 . . . . . . 7 (12 + 3) = 15
192 5p1e6 11466 . . . . . . 7 (5 + 1) = 6
19310, 11, 29, 9, 111, 188, 191, 192decadd 11833 . . . . . 6 (125 + 31) = 156
194114oveq1i 6894 . . . . . . . . 9 ((1 + 1) + 1) = (2 + 1)
195194, 73eqtri 2839 . . . . . . . 8 ((1 + 1) + 1) = 3
196 7p5e12 11856 . . . . . . . . 9 (7 + 5) = 12
19756, 92, 196addcomli 10523 . . . . . . . 8 (5 + 7) = 12
1989, 11, 9, 35, 88, 181, 195, 3, 197decaddc 11834 . . . . . . 7 (15 + 17) = 32
199 eqid 2817 . . . . . . . 8 34 = 34
200 7p3e10 11854 . . . . . . . . 9 (7 + 3) = 10
20156, 99, 200addcomli 10523 . . . . . . . 8 (3 + 7) = 10
20299mulid1i 10339 . . . . . . . . . 10 (3 · 1) = 3
20316addid1i 10518 . . . . . . . . . 10 (1 + 0) = 1
204202, 203oveq12i 6896 . . . . . . . . 9 ((3 · 1) + (1 + 0)) = (3 + 1)
205 3p1e4 11464 . . . . . . . . 9 (3 + 1) = 4
206204, 205eqtri 2839 . . . . . . . 8 ((3 · 1) + (1 + 0)) = 4
207 4cn 11399 . . . . . . . . . . 11 4 ∈ ℂ
208207mulid1i 10339 . . . . . . . . . 10 (4 · 1) = 4
209208oveq1i 6894 . . . . . . . . 9 ((4 · 1) + 0) = (4 + 0)
210207addid1i 10518 . . . . . . . . 9 (4 + 0) = 4
21130dec0h 11801 . . . . . . . . 9 4 = 04
212209, 210, 2113eqtri 2843 . . . . . . . 8 ((4 · 1) + 0) = 04
21329, 30, 9, 39, 199, 201, 9, 30, 39, 206, 212decmac 11831 . . . . . . 7 ((34 · 1) + (3 + 7)) = 44
2143dec0h 11801 . . . . . . . 8 2 = 02
215100, 145oveq12i 6896 . . . . . . . . 9 ((3 · 2) + (0 + 1)) = (6 + 1)
216 6p1e7 11467 . . . . . . . . 9 (6 + 1) = 7
217215, 216eqtri 2839 . . . . . . . 8 ((3 · 2) + (0 + 1)) = 7
218 4t2e8 11487 . . . . . . . . . 10 (4 · 2) = 8
219218oveq1i 6894 . . . . . . . . 9 ((4 · 2) + 2) = (8 + 2)
220 8p2e10 11859 . . . . . . . . 9 (8 + 2) = 10
221219, 220eqtri 2839 . . . . . . . 8 ((4 · 2) + 2) = 10
22229, 30, 39, 3, 199, 214, 3, 39, 9, 217, 221decmac 11831 . . . . . . 7 ((34 · 2) + 2) = 70
2239, 3, 29, 3, 113, 198, 31, 39, 35, 213, 222decma2c 11832 . . . . . 6 ((34 · 12) + (15 + 17)) = 440
224 5t3e15 11880 . . . . . . . . 9 (5 · 3) = 15
22592, 99, 224mulcomli 10344 . . . . . . . 8 (3 · 5) = 15
226 5p2e7 11475 . . . . . . . 8 (5 + 2) = 7
2279, 11, 3, 225, 226decaddi 11839 . . . . . . 7 ((3 · 5) + 2) = 17
228 5t4e20 11881 . . . . . . . . 9 (5 · 4) = 20
22992, 207, 228mulcomli 10344 . . . . . . . 8 (4 · 5) = 20
23061addid2i 10519 . . . . . . . 8 (0 + 6) = 6
2313, 39, 2, 229, 230decaddi 11839 . . . . . . 7 ((4 · 5) + 6) = 26
23229, 30, 2, 199, 11, 2, 3, 227, 231decrmac 11837 . . . . . 6 ((34 · 5) + 6) = 176
23310, 11, 46, 2, 111, 193, 31, 2, 36, 223, 232decma2c 11832 . . . . 5 ((34 · 125) + (125 + 31)) = 4406
234 9cn 11419 . . . . . . . 8 9 ∈ ℂ
235 9t3e27 11902 . . . . . . . 8 (9 · 3) = 27
236234, 99, 235mulcomli 10344 . . . . . . 7 (3 · 9) = 27
237 7p4e11 11855 . . . . . . 7 (7 + 4) = 11
2383, 35, 30, 236, 73, 9, 237decaddci 11840 . . . . . 6 ((3 · 9) + 4) = 31
239 9t4e36 11903 . . . . . . . 8 (9 · 4) = 36
240234, 207, 239mulcomli 10344 . . . . . . 7 (4 · 9) = 36
241151, 61, 172addcomli 10523 . . . . . . 7 (6 + 8) = 14
24229, 2, 13, 240, 205, 30, 241decaddci 11840 . . . . . 6 ((4 · 9) + 8) = 44
24329, 30, 13, 199, 5, 30, 30, 238, 242decrmac 11837 . . . . 5 ((34 · 9) + 8) = 314
24412, 5, 12, 13, 17, 22, 31, 30, 187, 233, 243decma2c 11832 . . . 4 ((34 · 𝑁) + (𝑁 − 1)) = 44064
245 eqid 2817 . . . . 5 136 = 136
2469, 5deccl 11794 . . . . . 6 19 ∈ ℕ0
247246, 30deccl 11794 . . . . 5 194 ∈ ℕ0
248 eqid 2817 . . . . . 6 13 = 13
249 eqid 2817 . . . . . 6 194 = 194
2505, 35deccl 11794 . . . . . 6 97 ∈ ℕ0
2519, 9deccl 11794 . . . . . . 7 11 ∈ ℕ0
252 eqid 2817 . . . . . . 7 324 = 324
253 eqid 2817 . . . . . . . 8 19 = 19
254 eqid 2817 . . . . . . . 8 97 = 97
255234, 16, 120addcomli 10523 . . . . . . . . 9 (1 + 9) = 10
2569, 39, 145, 255decsuc 11810 . . . . . . . 8 ((1 + 9) + 1) = 11
257 9p7e16 11871 . . . . . . . 8 (9 + 7) = 16
2589, 5, 5, 35, 253, 254, 256, 2, 257decaddc 11834 . . . . . . 7 (19 + 97) = 116
259 eqid 2817 . . . . . . . 8 32 = 32
260 eqid 2817 . . . . . . . . 9 11 = 11
2619, 9, 114, 260decsuc 11810 . . . . . . . 8 (11 + 1) = 12
26289oveq1i 6894 . . . . . . . . 9 ((2 · 1) + 2) = (2 + 2)
263262, 115, 2113eqtri 2843 . . . . . . . 8 ((2 · 1) + 2) = 04
26429, 3, 9, 3, 259, 261, 9, 30, 39, 206, 263decmac 11831 . . . . . . 7 ((32 · 1) + (11 + 1)) = 44
265208oveq1i 6894 . . . . . . . 8 ((4 · 1) + 6) = (4 + 6)
266 6p4e10 11851 . . . . . . . . 9 (6 + 4) = 10
26761, 207, 266addcomli 10523 . . . . . . . 8 (4 + 6) = 10
268265, 267eqtri 2839 . . . . . . 7 ((4 · 1) + 6) = 10
26933, 30, 251, 2, 252, 258, 9, 39, 9, 264, 268decmac 11831 . . . . . 6 ((324 · 1) + (19 + 97)) = 440
270145, 138eqtri 2839 . . . . . . . 8 (0 + 1) = 01
271 3t3e9 11486 . . . . . . . . . 10 (3 · 3) = 9
272271, 139oveq12i 6896 . . . . . . . . 9 ((3 · 3) + (0 + 0)) = (9 + 0)
273234addid1i 10518 . . . . . . . . 9 (9 + 0) = 9
274272, 273eqtri 2839 . . . . . . . 8 ((3 · 3) + (0 + 0)) = 9
275101oveq1i 6894 . . . . . . . . 9 ((2 · 3) + 1) = (6 + 1)
27635dec0h 11801 . . . . . . . . 9 7 = 07
277275, 216, 2763eqtri 2843 . . . . . . . 8 ((2 · 3) + 1) = 07
27829, 3, 39, 9, 259, 270, 29, 35, 39, 274, 277decmac 11831 . . . . . . 7 ((32 · 3) + (0 + 1)) = 97
279 4t3e12 11877 . . . . . . . 8 (4 · 3) = 12
280 4p2e6 11472 . . . . . . . . 9 (4 + 2) = 6
281207, 57, 280addcomli 10523 . . . . . . . 8 (2 + 4) = 6
2829, 3, 30, 279, 281decaddi 11839 . . . . . . 7 ((4 · 3) + 4) = 16
28333, 30, 39, 30, 252, 211, 29, 2, 9, 278, 282decmac 11831 . . . . . 6 ((324 · 3) + 4) = 976
2849, 29, 246, 30, 248, 249, 34, 2, 250, 269, 283decma2c 11832 . . . . 5 ((324 · 13) + 194) = 4406
285 6t3e18 11884 . . . . . . . . 9 (6 · 3) = 18
28661, 99, 285mulcomli 10344 . . . . . . . 8 (3 · 6) = 18
2879, 13, 18, 286decsuc 11810 . . . . . . 7 ((3 · 6) + 1) = 19
2889, 3, 3, 63, 115decaddi 11839 . . . . . . 7 ((2 · 6) + 2) = 14
28929, 3, 3, 259, 2, 30, 9, 287, 288decrmac 11837 . . . . . 6 ((32 · 6) + 2) = 194
290 6t4e24 11885 . . . . . . 7 (6 · 4) = 24
29161, 207, 290mulcomli 10344 . . . . . 6 (4 · 6) = 24
2922, 33, 30, 252, 30, 3, 289, 291decmul1c 11844 . . . . 5 (324 · 6) = 1944
29334, 37, 2, 245, 30, 247, 284, 292decmul2c 11845 . . . 4 (324 · 136) = 44064
294244, 293eqtr4i 2842 . . 3 ((34 · 𝑁) + (𝑁 − 1)) = (324 · 136)
29526, 1, 28, 32, 34, 23, 36, 38, 178, 179, 186, 294modxai 16009 . 2 ((2↑629) mod 𝑁) = ((𝑁 − 1) mod 𝑁)
296 eqid 2817 . . . 4 629 = 629
297 eqid 2817 . . . . 5 62 = 62
298139oveq2i 6895 . . . . . 6 ((2 · 6) + (0 + 0)) = ((2 · 6) + 0)
29963oveq1i 6894 . . . . . 6 ((2 · 6) + 0) = (12 + 0)
30010nn0cni 11591 . . . . . . 7 12 ∈ ℂ
301300addid1i 10518 . . . . . 6 (12 + 0) = 12
302298, 299, 3013eqtri 2843 . . . . 5 ((2 · 6) + (0 + 0)) = 12
30311dec0h 11801 . . . . . 6 5 = 05
30481, 55, 3033eqtri 2843 . . . . 5 ((2 · 2) + 1) = 05
3052, 3, 39, 9, 297, 138, 3, 11, 39, 302, 304decma2c 11832 . . . 4 ((2 · 62) + 1) = 125
306 9t2e18 11901 . . . . 5 (9 · 2) = 18
307234, 57, 306mulcomli 10344 . . . 4 (2 · 9) = 18
3083, 4, 5, 296, 13, 9, 305, 307decmul2c 11845 . . 3 (2 · 629) = 1258
309308, 22eqtr4i 2842 . 2 (2 · 629) = (𝑁 − 1)
310 npcan 10585 . . 3 ((𝑁 ∈ ℂ ∧ 1 ∈ ℂ) → ((𝑁 − 1) + 1) = 𝑁)
31167, 16, 310mp2an 675 . 2 ((𝑁 − 1) + 1) = 𝑁
31268oveq1i 6894 . . 3 ((0 · 𝑁) + 1) = (0 + 1)
313145, 312, 1613eqtr4i 2849 . 2 ((0 · 𝑁) + 1) = (1 · 1)
3141, 6, 7, 8, 9, 23, 295, 309, 311, 313mod2xnegi 16012 1 ((2↑(𝑁 − 1)) mod 𝑁) = (1 mod 𝑁)
Colors of variables: wff setvar class
Syntax hints:   = wceq 1637  wcel 2157  (class class class)co 6884  cc 10229  0cc0 10231  1c1 10232   + caddc 10234   · cmul 10236  cmin 10561  cn 11315  2c2 11368  3c3 11369  4c4 11370  5c5 11371  6c6 11372  7c7 11373  8c8 11374  9c9 11375  0cn0 11579  cdc 11779   mod cmo 12912  cexp 13103
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1877  ax-4 1894  ax-5 2001  ax-6 2069  ax-7 2105  ax-8 2159  ax-9 2166  ax-10 2186  ax-11 2202  ax-12 2215  ax-13 2422  ax-ext 2795  ax-sep 4988  ax-nul 4996  ax-pow 5048  ax-pr 5109  ax-un 7189  ax-cnex 10287  ax-resscn 10288  ax-1cn 10289  ax-icn 10290  ax-addcl 10291  ax-addrcl 10292  ax-mulcl 10293  ax-mulrcl 10294  ax-mulcom 10295  ax-addass 10296  ax-mulass 10297  ax-distr 10298  ax-i2m1 10299  ax-1ne0 10300  ax-1rid 10301  ax-rnegex 10302  ax-rrecex 10303  ax-cnre 10304  ax-pre-lttri 10305  ax-pre-lttrn 10306  ax-pre-ltadd 10307  ax-pre-mulgt0 10308  ax-pre-sup 10309
This theorem depends on definitions:  df-bi 198  df-an 385  df-or 866  df-3or 1101  df-3an 1102  df-tru 1641  df-ex 1860  df-nf 1864  df-sb 2062  df-mo 2635  df-eu 2642  df-clab 2804  df-cleq 2810  df-clel 2813  df-nfc 2948  df-ne 2990  df-nel 3093  df-ral 3112  df-rex 3113  df-reu 3114  df-rmo 3115  df-rab 3116  df-v 3404  df-sbc 3645  df-csb 3740  df-dif 3783  df-un 3785  df-in 3787  df-ss 3794  df-pss 3796  df-nul 4128  df-if 4291  df-pw 4364  df-sn 4382  df-pr 4384  df-tp 4386  df-op 4388  df-uni 4642  df-iun 4725  df-br 4856  df-opab 4918  df-mpt 4935  df-tr 4958  df-id 5232  df-eprel 5237  df-po 5245  df-so 5246  df-fr 5283  df-we 5285  df-xp 5330  df-rel 5331  df-cnv 5332  df-co 5333  df-dm 5334  df-rn 5335  df-res 5336  df-ima 5337  df-pred 5907  df-ord 5953  df-on 5954  df-lim 5955  df-suc 5956  df-iota 6074  df-fun 6113  df-fn 6114  df-f 6115  df-f1 6116  df-fo 6117  df-f1o 6118  df-fv 6119  df-riota 6845  df-ov 6887  df-oprab 6888  df-mpt2 6889  df-om 7306  df-2nd 7409  df-wrecs 7652  df-recs 7714  df-rdg 7752  df-er 7989  df-en 8203  df-dom 8204  df-sdom 8205  df-sup 8597  df-inf 8598  df-pnf 10371  df-mnf 10372  df-xr 10373  df-ltxr 10374  df-le 10375  df-sub 10563  df-neg 10564  df-div 10980  df-nn 11316  df-2 11376  df-3 11377  df-4 11378  df-5 11379  df-6 11380  df-7 11381  df-8 11382  df-9 11383  df-n0 11580  df-z 11664  df-dec 11780  df-uz 11925  df-rp 12067  df-fl 12837  df-mod 12913  df-seq 13045  df-exp 13104
This theorem is referenced by:  1259prm  16074
  Copyright terms: Public domain W3C validator