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

Theorem 1259lem2 16070
Description: Lemma for 1259prm 16074. Calculate a power mod. In decimal, we calculate 2↑34 = (2↑17)↑2≡136↑2≡14𝑁 + 870. (Contributed by Mario Carneiro, 22-Feb-2014.) (Revised by Mario Carneiro, 20-Apr-2015.) (Proof shortened by AV, 15-Sep-2021.)
Hypothesis
Ref Expression
1259prm.1 𝑁 = 1259
Assertion
Ref Expression
1259lem2 ((2↑34) mod 𝑁) = (870 mod 𝑁)

Proof of Theorem 1259lem2
StepHypRef Expression
1 1259prm.1 . . 3 𝑁 = 1259
2 1nn0 11595 . . . . . 6 1 ∈ ℕ0
3 2nn0 11596 . . . . . 6 2 ∈ ℕ0
42, 3deccl 11794 . . . . 5 12 ∈ ℕ0
5 5nn0 11599 . . . . 5 5 ∈ ℕ0
64, 5deccl 11794 . . . 4 125 ∈ ℕ0
7 9nn 11417 . . . 4 9 ∈ ℕ
86, 7decnncl 11799 . . 3 1259 ∈ ℕ
91, 8eqeltri 2892 . 2 𝑁 ∈ ℕ
10 2nn 11386 . 2 2 ∈ ℕ
11 7nn0 11601 . . 3 7 ∈ ℕ0
122, 11deccl 11794 . 2 17 ∈ ℕ0
13 4nn0 11598 . . . 4 4 ∈ ℕ0
142, 13deccl 11794 . . 3 14 ∈ ℕ0
1514nn0zi 11688 . 2 14 ∈ ℤ
16 3nn0 11597 . . . 4 3 ∈ ℕ0
172, 16deccl 11794 . . 3 13 ∈ ℕ0
18 6nn0 11600 . . 3 6 ∈ ℕ0
1917, 18deccl 11794 . 2 136 ∈ ℕ0
20 8nn0 11602 . . . 4 8 ∈ ℕ0
2120, 11deccl 11794 . . 3 87 ∈ ℕ0
22 0nn0 11594 . . 3 0 ∈ ℕ0
2321, 22deccl 11794 . 2 870 ∈ ℕ0
2411259lem1 16069 . 2 ((2↑17) mod 𝑁) = (136 mod 𝑁)
25 eqid 2817 . . 3 17 = 17
26 2cn 11388 . . . . . 6 2 ∈ ℂ
2726mulid1i 10339 . . . . 5 (2 · 1) = 2
2827oveq1i 6894 . . . 4 ((2 · 1) + 1) = (2 + 1)
29 2p1e3 11462 . . . 4 (2 + 1) = 3
3028, 29eqtri 2839 . . 3 ((2 · 1) + 1) = 3
31 7cn 11411 . . . 4 7 ∈ ℂ
32 7t2e14 11888 . . . 4 (7 · 2) = 14
3331, 26, 32mulcomli 10344 . . 3 (2 · 7) = 14
343, 2, 11, 25, 13, 2, 30, 33decmul2c 11845 . 2 (2 · 17) = 34
35 9nn0 11603 . . . 4 9 ∈ ℕ0
36 eqid 2817 . . . 4 870 = 870
37 eqid 2817 . . . . 5 125 = 125
38 eqid 2817 . . . . . 6 87 = 87
39 eqid 2817 . . . . . 6 12 = 12
40 8p1e9 11469 . . . . . 6 (8 + 1) = 9
41 7p2e9 11480 . . . . . 6 (7 + 2) = 9
4220, 11, 2, 3, 38, 39, 40, 41decadd 11833 . . . . 5 (87 + 12) = 99
43 9p7e16 11871 . . . . . 6 (9 + 7) = 16
44 eqid 2817 . . . . . . 7 14 = 14
45 3cn 11394 . . . . . . . . 9 3 ∈ ℂ
46 ax-1cn 10289 . . . . . . . . 9 1 ∈ ℂ
47 3p1e4 11464 . . . . . . . . 9 (3 + 1) = 4
4845, 46, 47addcomli 10523 . . . . . . . 8 (1 + 3) = 4
4913dec0h 11801 . . . . . . . 8 4 = 04
5048, 49eqtri 2839 . . . . . . 7 (1 + 3) = 04
5146mulid1i 10339 . . . . . . . . 9 (1 · 1) = 1
52 00id 10506 . . . . . . . . 9 (0 + 0) = 0
5351, 52oveq12i 6896 . . . . . . . 8 ((1 · 1) + (0 + 0)) = (1 + 0)
5446addid1i 10518 . . . . . . . 8 (1 + 0) = 1
5553, 54eqtri 2839 . . . . . . 7 ((1 · 1) + (0 + 0)) = 1
56 4cn 11399 . . . . . . . . . 10 4 ∈ ℂ
5756mulid1i 10339 . . . . . . . . 9 (4 · 1) = 4
5857oveq1i 6894 . . . . . . . 8 ((4 · 1) + 4) = (4 + 4)
59 4p4e8 11474 . . . . . . . 8 (4 + 4) = 8
6020dec0h 11801 . . . . . . . 8 8 = 08
6158, 59, 603eqtri 2843 . . . . . . 7 ((4 · 1) + 4) = 08
622, 13, 22, 13, 44, 50, 2, 20, 22, 55, 61decmac 11831 . . . . . 6 ((14 · 1) + (1 + 3)) = 18
6318dec0h 11801 . . . . . . 7 6 = 06
6426mulid2i 10340 . . . . . . . . 9 (1 · 2) = 2
6546addid2i 10519 . . . . . . . . 9 (0 + 1) = 1
6664, 65oveq12i 6896 . . . . . . . 8 ((1 · 2) + (0 + 1)) = (2 + 1)
6766, 29eqtri 2839 . . . . . . 7 ((1 · 2) + (0 + 1)) = 3
68 4t2e8 11487 . . . . . . . . 9 (4 · 2) = 8
6968oveq1i 6894 . . . . . . . 8 ((4 · 2) + 6) = (8 + 6)
70 8p6e14 11863 . . . . . . . 8 (8 + 6) = 14
7169, 70eqtri 2839 . . . . . . 7 ((4 · 2) + 6) = 14
722, 13, 22, 18, 44, 63, 3, 13, 2, 67, 71decmac 11831 . . . . . 6 ((14 · 2) + 6) = 34
732, 3, 2, 18, 39, 43, 14, 13, 16, 62, 72decma2c 11832 . . . . 5 ((14 · 12) + (9 + 7)) = 184
7435dec0h 11801 . . . . . 6 9 = 09
75 5cn 11403 . . . . . . . . 9 5 ∈ ℂ
7675mulid2i 10340 . . . . . . . 8 (1 · 5) = 5
7726addid2i 10519 . . . . . . . 8 (0 + 2) = 2
7876, 77oveq12i 6896 . . . . . . 7 ((1 · 5) + (0 + 2)) = (5 + 2)
79 5p2e7 11475 . . . . . . 7 (5 + 2) = 7
8078, 79eqtri 2839 . . . . . 6 ((1 · 5) + (0 + 2)) = 7
81 5t4e20 11881 . . . . . . . 8 (5 · 4) = 20
8275, 56, 81mulcomli 10344 . . . . . . 7 (4 · 5) = 20
83 9cn 11419 . . . . . . . 8 9 ∈ ℂ
8483addid2i 10519 . . . . . . 7 (0 + 9) = 9
853, 22, 35, 82, 84decaddi 11839 . . . . . 6 ((4 · 5) + 9) = 29
862, 13, 22, 35, 44, 74, 5, 35, 3, 80, 85decmac 11831 . . . . 5 ((14 · 5) + 9) = 79
874, 5, 35, 35, 37, 42, 14, 35, 11, 73, 86decma2c 11832 . . . 4 ((14 · 125) + (87 + 12)) = 1849
8883mulid2i 10340 . . . . . . . . 9 (1 · 9) = 9
8988oveq1i 6894 . . . . . . . 8 ((1 · 9) + 3) = (9 + 3)
90 9p3e12 11867 . . . . . . . 8 (9 + 3) = 12
9189, 90eqtri 2839 . . . . . . 7 ((1 · 9) + 3) = 12
92 9t4e36 11903 . . . . . . . 8 (9 · 4) = 36
9383, 56, 92mulcomli 10344 . . . . . . 7 (4 · 9) = 36
9435, 2, 13, 44, 18, 16, 91, 93decmul1c 11844 . . . . . 6 (14 · 9) = 126
9594oveq1i 6894 . . . . 5 ((14 · 9) + 0) = (126 + 0)
964, 18deccl 11794 . . . . . . 7 126 ∈ ℕ0
9796nn0cni 11591 . . . . . 6 126 ∈ ℂ
9897addid1i 10518 . . . . 5 (126 + 0) = 126
9995, 98eqtri 2839 . . . 4 ((14 · 9) + 0) = 126
1006, 35, 21, 22, 1, 36, 14, 18, 4, 87, 99decma2c 11832 . . 3 ((14 · 𝑁) + 870) = 18496
101 eqid 2817 . . . 4 136 = 136
10220, 2deccl 11794 . . . 4 81 ∈ ℕ0
103 eqid 2817 . . . . 5 13 = 13
104 eqid 2817 . . . . 5 81 = 81
10513, 22deccl 11794 . . . . 5 40 ∈ ℕ0
106 eqid 2817 . . . . . . 7 40 = 40
10756addid2i 10519 . . . . . . 7 (0 + 4) = 4
108 8cn 11415 . . . . . . . 8 8 ∈ ℂ
109108addid1i 10518 . . . . . . 7 (8 + 0) = 8
11022, 20, 13, 22, 60, 106, 107, 109decadd 11833 . . . . . 6 (8 + 40) = 48
111 4p1e5 11465 . . . . . . . 8 (4 + 1) = 5
1125dec0h 11801 . . . . . . . 8 5 = 05
113111, 112eqtri 2839 . . . . . . 7 (4 + 1) = 05
11445mulid1i 10339 . . . . . . . . 9 (3 · 1) = 3
115114oveq1i 6894 . . . . . . . 8 ((3 · 1) + 5) = (3 + 5)
116 5p3e8 11476 . . . . . . . . 9 (5 + 3) = 8
11775, 45, 116addcomli 10523 . . . . . . . 8 (3 + 5) = 8
118115, 117, 603eqtri 2843 . . . . . . 7 ((3 · 1) + 5) = 08
1192, 16, 22, 5, 103, 113, 2, 20, 22, 55, 118decmac 11831 . . . . . 6 ((13 · 1) + (4 + 1)) = 18
120 6cn 11407 . . . . . . . . 9 6 ∈ ℂ
121120mulid1i 10339 . . . . . . . 8 (6 · 1) = 6
122121oveq1i 6894 . . . . . . 7 ((6 · 1) + 8) = (6 + 8)
123108, 120, 70addcomli 10523 . . . . . . 7 (6 + 8) = 14
124122, 123eqtri 2839 . . . . . 6 ((6 · 1) + 8) = 14
12517, 18, 13, 20, 101, 110, 2, 13, 2, 119, 124decmac 11831 . . . . 5 ((136 · 1) + (8 + 40)) = 184
1262dec0h 11801 . . . . . 6 1 = 01
12765, 126eqtri 2839 . . . . . . 7 (0 + 1) = 01
12845mulid2i 10340 . . . . . . . . 9 (1 · 3) = 3
129128, 65oveq12i 6896 . . . . . . . 8 ((1 · 3) + (0 + 1)) = (3 + 1)
130129, 47eqtri 2839 . . . . . . 7 ((1 · 3) + (0 + 1)) = 4
131 3t3e9 11486 . . . . . . . . 9 (3 · 3) = 9
132131oveq1i 6894 . . . . . . . 8 ((3 · 3) + 1) = (9 + 1)
133 9p1e10 11781 . . . . . . . 8 (9 + 1) = 10
134132, 133eqtri 2839 . . . . . . 7 ((3 · 3) + 1) = 10
1352, 16, 22, 2, 103, 127, 16, 22, 2, 130, 134decmac 11831 . . . . . 6 ((13 · 3) + (0 + 1)) = 40
136 6t3e18 11884 . . . . . . 7 (6 · 3) = 18
1372, 20, 2, 136, 40decaddi 11839 . . . . . 6 ((6 · 3) + 1) = 19
13817, 18, 22, 2, 101, 126, 16, 35, 2, 135, 137decmac 11831 . . . . 5 ((136 · 3) + 1) = 409
1392, 16, 20, 2, 103, 104, 19, 35, 105, 125, 138decma2c 11832 . . . 4 ((136 · 13) + 81) = 1849
14016dec0h 11801 . . . . . 6 3 = 03
141120mulid2i 10340 . . . . . . . 8 (1 · 6) = 6
142141, 77oveq12i 6896 . . . . . . 7 ((1 · 6) + (0 + 2)) = (6 + 2)
143 6p2e8 11478 . . . . . . 7 (6 + 2) = 8
144142, 143eqtri 2839 . . . . . 6 ((1 · 6) + (0 + 2)) = 8
145120, 45, 136mulcomli 10344 . . . . . . 7 (3 · 6) = 18
146 1p1e2 11445 . . . . . . 7 (1 + 1) = 2
147 8p3e11 11860 . . . . . . 7 (8 + 3) = 11
1482, 20, 16, 145, 146, 2, 147decaddci 11840 . . . . . 6 ((3 · 6) + 3) = 21
1492, 16, 22, 16, 103, 140, 18, 2, 3, 144, 148decmac 11831 . . . . 5 ((13 · 6) + 3) = 81
150 6t6e36 11887 . . . . 5 (6 · 6) = 36
15118, 17, 18, 101, 18, 16, 149, 150decmul1c 11844 . . . 4 (136 · 6) = 816
15219, 17, 18, 101, 18, 102, 139, 151decmul2c 11845 . . 3 (136 · 136) = 18496
153100, 152eqtr4i 2842 . 2 ((14 · 𝑁) + 870) = (136 · 136)
1549, 10, 12, 15, 19, 23, 24, 34, 153mod2xi 16010 1 ((2↑34) mod 𝑁) = (870 mod 𝑁)
Colors of variables: wff setvar class
Syntax hints:   = wceq 1637  (class class class)co 6884  0cc0 10231  1c1 10232   + caddc 10234   · cmul 10236  cn 11315  2c2 11368  3c3 11369  4c4 11370  5c5 11371  6c6 11372  7c7 11373  8c8 11374  9c9 11375  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:  1259lem3  16071  1259lem5  16073
  Copyright terms: Public domain W3C validator