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

Theorem 1259lem2 16311
Description: Lemma for 1259prm 16315. 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 11718 . . . . . 6 1 ∈ ℕ0
3 2nn0 11719 . . . . . 6 2 ∈ ℕ0
42, 3deccl 11919 . . . . 5 12 ∈ ℕ0
5 5nn0 11722 . . . . 5 5 ∈ ℕ0
64, 5deccl 11919 . . . 4 125 ∈ ℕ0
7 9nn 11537 . . . 4 9 ∈ ℕ
86, 7decnncl 11925 . . 3 1259 ∈ ℕ
91, 8eqeltri 2856 . 2 𝑁 ∈ ℕ
10 2nn 11506 . 2 2 ∈ ℕ
11 7nn0 11724 . . 3 7 ∈ ℕ0
122, 11deccl 11919 . 2 17 ∈ ℕ0
13 4nn0 11721 . . . 4 4 ∈ ℕ0
142, 13deccl 11919 . . 3 14 ∈ ℕ0
1514nn0zi 11813 . 2 14 ∈ ℤ
16 3nn0 11720 . . . 4 3 ∈ ℕ0
172, 16deccl 11919 . . 3 13 ∈ ℕ0
18 6nn0 11723 . . 3 6 ∈ ℕ0
1917, 18deccl 11919 . 2 136 ∈ ℕ0
20 8nn0 11725 . . . 4 8 ∈ ℕ0
2120, 11deccl 11919 . . 3 87 ∈ ℕ0
22 0nn0 11717 . . 3 0 ∈ ℕ0
2321, 22deccl 11919 . 2 870 ∈ ℕ0
2411259lem1 16310 . 2 ((2↑17) mod 𝑁) = (136 mod 𝑁)
25 eqid 2772 . . 3 17 = 17
26 2cn 11508 . . . . . 6 2 ∈ ℂ
2726mulid1i 10436 . . . . 5 (2 · 1) = 2
2827oveq1i 6980 . . . 4 ((2 · 1) + 1) = (2 + 1)
29 2p1e3 11582 . . . 4 (2 + 1) = 3
3028, 29eqtri 2796 . . 3 ((2 · 1) + 1) = 3
31 7cn 11531 . . . 4 7 ∈ ℂ
32 7t2e14 12015 . . . 4 (7 · 2) = 14
3331, 26, 32mulcomli 10441 . . 3 (2 · 7) = 14
343, 2, 11, 25, 13, 2, 30, 33decmul2c 11972 . 2 (2 · 17) = 34
35 9nn0 11726 . . . 4 9 ∈ ℕ0
36 eqid 2772 . . . 4 870 = 870
37 eqid 2772 . . . . 5 125 = 125
38 eqid 2772 . . . . . 6 87 = 87
39 eqid 2772 . . . . . 6 12 = 12
40 8p1e9 11590 . . . . . 6 (8 + 1) = 9
41 7p2e9 11601 . . . . . 6 (7 + 2) = 9
4220, 11, 2, 3, 38, 39, 40, 41decadd 11959 . . . . 5 (87 + 12) = 99
43 9p7e16 11998 . . . . . 6 (9 + 7) = 16
44 eqid 2772 . . . . . . 7 14 = 14
45 3cn 11514 . . . . . . . . 9 3 ∈ ℂ
46 ax-1cn 10385 . . . . . . . . 9 1 ∈ ℂ
47 3p1e4 11585 . . . . . . . . 9 (3 + 1) = 4
4845, 46, 47addcomli 10624 . . . . . . . 8 (1 + 3) = 4
4913dec0h 11927 . . . . . . . 8 4 = 04
5048, 49eqtri 2796 . . . . . . 7 (1 + 3) = 04
5146mulid1i 10436 . . . . . . . . 9 (1 · 1) = 1
52 00id 10607 . . . . . . . . 9 (0 + 0) = 0
5351, 52oveq12i 6982 . . . . . . . 8 ((1 · 1) + (0 + 0)) = (1 + 0)
5446addid1i 10619 . . . . . . . 8 (1 + 0) = 1
5553, 54eqtri 2796 . . . . . . 7 ((1 · 1) + (0 + 0)) = 1
56 4cn 11519 . . . . . . . . . 10 4 ∈ ℂ
5756mulid1i 10436 . . . . . . . . 9 (4 · 1) = 4
5857oveq1i 6980 . . . . . . . 8 ((4 · 1) + 4) = (4 + 4)
59 4p4e8 11595 . . . . . . . 8 (4 + 4) = 8
6020dec0h 11927 . . . . . . . 8 8 = 08
6158, 59, 603eqtri 2800 . . . . . . 7 ((4 · 1) + 4) = 08
622, 13, 22, 13, 44, 50, 2, 20, 22, 55, 61decmac 11957 . . . . . 6 ((14 · 1) + (1 + 3)) = 18
6318dec0h 11927 . . . . . . 7 6 = 06
6426mulid2i 10437 . . . . . . . . 9 (1 · 2) = 2
6546addid2i 10620 . . . . . . . . 9 (0 + 1) = 1
6664, 65oveq12i 6982 . . . . . . . 8 ((1 · 2) + (0 + 1)) = (2 + 1)
6766, 29eqtri 2796 . . . . . . 7 ((1 · 2) + (0 + 1)) = 3
68 4t2e8 11608 . . . . . . . . 9 (4 · 2) = 8
6968oveq1i 6980 . . . . . . . 8 ((4 · 2) + 6) = (8 + 6)
70 8p6e14 11990 . . . . . . . 8 (8 + 6) = 14
7169, 70eqtri 2796 . . . . . . 7 ((4 · 2) + 6) = 14
722, 13, 22, 18, 44, 63, 3, 13, 2, 67, 71decmac 11957 . . . . . 6 ((14 · 2) + 6) = 34
732, 3, 2, 18, 39, 43, 14, 13, 16, 62, 72decma2c 11958 . . . . 5 ((14 · 12) + (9 + 7)) = 184
7435dec0h 11927 . . . . . 6 9 = 09
75 5cn 11523 . . . . . . . . 9 5 ∈ ℂ
7675mulid2i 10437 . . . . . . . 8 (1 · 5) = 5
7726addid2i 10620 . . . . . . . 8 (0 + 2) = 2
7876, 77oveq12i 6982 . . . . . . 7 ((1 · 5) + (0 + 2)) = (5 + 2)
79 5p2e7 11596 . . . . . . 7 (5 + 2) = 7
8078, 79eqtri 2796 . . . . . 6 ((1 · 5) + (0 + 2)) = 7
81 5t4e20 12008 . . . . . . . 8 (5 · 4) = 20
8275, 56, 81mulcomli 10441 . . . . . . 7 (4 · 5) = 20
83 9cn 11539 . . . . . . . 8 9 ∈ ℂ
8483addid2i 10620 . . . . . . 7 (0 + 9) = 9
853, 22, 35, 82, 84decaddi 11965 . . . . . 6 ((4 · 5) + 9) = 29
862, 13, 22, 35, 44, 74, 5, 35, 3, 80, 85decmac 11957 . . . . 5 ((14 · 5) + 9) = 79
874, 5, 35, 35, 37, 42, 14, 35, 11, 73, 86decma2c 11958 . . . 4 ((14 · 125) + (87 + 12)) = 1849
8883mulid2i 10437 . . . . . . . . 9 (1 · 9) = 9
8988oveq1i 6980 . . . . . . . 8 ((1 · 9) + 3) = (9 + 3)
90 9p3e12 11994 . . . . . . . 8 (9 + 3) = 12
9189, 90eqtri 2796 . . . . . . 7 ((1 · 9) + 3) = 12
92 9t4e36 12030 . . . . . . . 8 (9 · 4) = 36
9383, 56, 92mulcomli 10441 . . . . . . 7 (4 · 9) = 36
9435, 2, 13, 44, 18, 16, 91, 93decmul1c 11971 . . . . . 6 (14 · 9) = 126
9594oveq1i 6980 . . . . 5 ((14 · 9) + 0) = (126 + 0)
964, 18deccl 11919 . . . . . . 7 126 ∈ ℕ0
9796nn0cni 11713 . . . . . 6 126 ∈ ℂ
9897addid1i 10619 . . . . 5 (126 + 0) = 126
9995, 98eqtri 2796 . . . 4 ((14 · 9) + 0) = 126
1006, 35, 21, 22, 1, 36, 14, 18, 4, 87, 99decma2c 11958 . . 3 ((14 · 𝑁) + 870) = 18496
101 eqid 2772 . . . 4 136 = 136
10220, 2deccl 11919 . . . 4 81 ∈ ℕ0
103 eqid 2772 . . . . 5 13 = 13
104 eqid 2772 . . . . 5 81 = 81
10513, 22deccl 11919 . . . . 5 40 ∈ ℕ0
106 eqid 2772 . . . . . . 7 40 = 40
10756addid2i 10620 . . . . . . 7 (0 + 4) = 4
108 8cn 11535 . . . . . . . 8 8 ∈ ℂ
109108addid1i 10619 . . . . . . 7 (8 + 0) = 8
11022, 20, 13, 22, 60, 106, 107, 109decadd 11959 . . . . . 6 (8 + 40) = 48
111 4p1e5 11586 . . . . . . . 8 (4 + 1) = 5
1125dec0h 11927 . . . . . . . 8 5 = 05
113111, 112eqtri 2796 . . . . . . 7 (4 + 1) = 05
11445mulid1i 10436 . . . . . . . . 9 (3 · 1) = 3
115114oveq1i 6980 . . . . . . . 8 ((3 · 1) + 5) = (3 + 5)
116 5p3e8 11597 . . . . . . . . 9 (5 + 3) = 8
11775, 45, 116addcomli 10624 . . . . . . . 8 (3 + 5) = 8
118115, 117, 603eqtri 2800 . . . . . . 7 ((3 · 1) + 5) = 08
1192, 16, 22, 5, 103, 113, 2, 20, 22, 55, 118decmac 11957 . . . . . 6 ((13 · 1) + (4 + 1)) = 18
120 6cn 11527 . . . . . . . . 9 6 ∈ ℂ
121120mulid1i 10436 . . . . . . . 8 (6 · 1) = 6
122121oveq1i 6980 . . . . . . 7 ((6 · 1) + 8) = (6 + 8)
123108, 120, 70addcomli 10624 . . . . . . 7 (6 + 8) = 14
124122, 123eqtri 2796 . . . . . 6 ((6 · 1) + 8) = 14
12517, 18, 13, 20, 101, 110, 2, 13, 2, 119, 124decmac 11957 . . . . 5 ((136 · 1) + (8 + 40)) = 184
1262dec0h 11927 . . . . . 6 1 = 01
12765, 126eqtri 2796 . . . . . . 7 (0 + 1) = 01
12845mulid2i 10437 . . . . . . . . 9 (1 · 3) = 3
129128, 65oveq12i 6982 . . . . . . . 8 ((1 · 3) + (0 + 1)) = (3 + 1)
130129, 47eqtri 2796 . . . . . . 7 ((1 · 3) + (0 + 1)) = 4
131 3t3e9 11607 . . . . . . . . 9 (3 · 3) = 9
132131oveq1i 6980 . . . . . . . 8 ((3 · 3) + 1) = (9 + 1)
133 9p1e10 11906 . . . . . . . 8 (9 + 1) = 10
134132, 133eqtri 2796 . . . . . . 7 ((3 · 3) + 1) = 10
1352, 16, 22, 2, 103, 127, 16, 22, 2, 130, 134decmac 11957 . . . . . 6 ((13 · 3) + (0 + 1)) = 40
136 6t3e18 12011 . . . . . . 7 (6 · 3) = 18
1372, 20, 2, 136, 40decaddi 11965 . . . . . 6 ((6 · 3) + 1) = 19
13817, 18, 22, 2, 101, 126, 16, 35, 2, 135, 137decmac 11957 . . . . 5 ((136 · 3) + 1) = 409
1392, 16, 20, 2, 103, 104, 19, 35, 105, 125, 138decma2c 11958 . . . 4 ((136 · 13) + 81) = 1849
14016dec0h 11927 . . . . . 6 3 = 03
141120mulid2i 10437 . . . . . . . 8 (1 · 6) = 6
142141, 77oveq12i 6982 . . . . . . 7 ((1 · 6) + (0 + 2)) = (6 + 2)
143 6p2e8 11599 . . . . . . 7 (6 + 2) = 8
144142, 143eqtri 2796 . . . . . 6 ((1 · 6) + (0 + 2)) = 8
145120, 45, 136mulcomli 10441 . . . . . . 7 (3 · 6) = 18
146 1p1e2 11565 . . . . . . 7 (1 + 1) = 2
147 8p3e11 11987 . . . . . . 7 (8 + 3) = 11
1482, 20, 16, 145, 146, 2, 147decaddci 11966 . . . . . 6 ((3 · 6) + 3) = 21
1492, 16, 22, 16, 103, 140, 18, 2, 3, 144, 148decmac 11957 . . . . 5 ((13 · 6) + 3) = 81
150 6t6e36 12014 . . . . 5 (6 · 6) = 36
15118, 17, 18, 101, 18, 16, 149, 150decmul1c 11971 . . . 4 (136 · 6) = 816
15219, 17, 18, 101, 18, 102, 139, 151decmul2c 11972 . . 3 (136 · 136) = 18496
153100, 152eqtr4i 2799 . 2 ((14 · 𝑁) + 870) = (136 · 136)
1549, 10, 12, 15, 19, 23, 24, 34, 153mod2xi 16251 1 ((2↑34) mod 𝑁) = (870 mod 𝑁)
Colors of variables: wff setvar class
Syntax hints:   = wceq 1507  (class class class)co 6970  0cc0 10327  1c1 10328   + caddc 10330   · cmul 10332  cn 11431  2c2 11488  3c3 11489  4c4 11490  5c5 11491  6c6 11492  7c7 11493  8c8 11494  9c9 11495  cdc 11904   mod cmo 13045  cexp 13237
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1758  ax-4 1772  ax-5 1869  ax-6 1928  ax-7 1964  ax-8 2050  ax-9 2057  ax-10 2077  ax-11 2091  ax-12 2104  ax-13 2299  ax-ext 2745  ax-sep 5054  ax-nul 5061  ax-pow 5113  ax-pr 5180  ax-un 7273  ax-cnex 10383  ax-resscn 10384  ax-1cn 10385  ax-icn 10386  ax-addcl 10387  ax-addrcl 10388  ax-mulcl 10389  ax-mulrcl 10390  ax-mulcom 10391  ax-addass 10392  ax-mulass 10393  ax-distr 10394  ax-i2m1 10395  ax-1ne0 10396  ax-1rid 10397  ax-rnegex 10398  ax-rrecex 10399  ax-cnre 10400  ax-pre-lttri 10401  ax-pre-lttrn 10402  ax-pre-ltadd 10403  ax-pre-mulgt0 10404  ax-pre-sup 10405
This theorem depends on definitions:  df-bi 199  df-an 388  df-or 834  df-3or 1069  df-3an 1070  df-tru 1510  df-ex 1743  df-nf 1747  df-sb 2014  df-mo 2544  df-eu 2580  df-clab 2754  df-cleq 2765  df-clel 2840  df-nfc 2912  df-ne 2962  df-nel 3068  df-ral 3087  df-rex 3088  df-reu 3089  df-rmo 3090  df-rab 3091  df-v 3411  df-sbc 3678  df-csb 3783  df-dif 3828  df-un 3830  df-in 3832  df-ss 3839  df-pss 3841  df-nul 4174  df-if 4345  df-pw 4418  df-sn 4436  df-pr 4438  df-tp 4440  df-op 4442  df-uni 4707  df-iun 4788  df-br 4924  df-opab 4986  df-mpt 5003  df-tr 5025  df-id 5305  df-eprel 5310  df-po 5319  df-so 5320  df-fr 5359  df-we 5361  df-xp 5406  df-rel 5407  df-cnv 5408  df-co 5409  df-dm 5410  df-rn 5411  df-res 5412  df-ima 5413  df-pred 5980  df-ord 6026  df-on 6027  df-lim 6028  df-suc 6029  df-iota 6146  df-fun 6184  df-fn 6185  df-f 6186  df-f1 6187  df-fo 6188  df-f1o 6189  df-fv 6190  df-riota 6931  df-ov 6973  df-oprab 6974  df-mpo 6975  df-om 7391  df-2nd 7495  df-wrecs 7743  df-recs 7805  df-rdg 7843  df-er 8081  df-en 8299  df-dom 8300  df-sdom 8301  df-sup 8693  df-inf 8694  df-pnf 10468  df-mnf 10469  df-xr 10470  df-ltxr 10471  df-le 10472  df-sub 10664  df-neg 10665  df-div 11091  df-nn 11432  df-2 11496  df-3 11497  df-4 11498  df-5 11499  df-6 11500  df-7 11501  df-8 11502  df-9 11503  df-n0 11701  df-z 11787  df-dec 11905  df-uz 12052  df-rp 12198  df-fl 12970  df-mod 13046  df-seq 13178  df-exp 13238
This theorem is referenced by:  1259lem3  16312  1259lem5  16314
  Copyright terms: Public domain W3C validator