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

Theorem 1259lem5 17064
Description: Lemma for 1259prm 17065. Calculate the GCD of 2↑34 − 1≡869 with 𝑁 = 1259. (Contributed by Mario Carneiro, 22-Feb-2014.) (Revised by Mario Carneiro, 20-Apr-2015.)
Hypothesis
Ref Expression
1259prm.1 𝑁 = 1259
Assertion
Ref Expression
1259lem5 (((2↑34) − 1) gcd 𝑁) = 1

Proof of Theorem 1259lem5
StepHypRef Expression
1 2nn 12281 . . . 4 2 ∈ ℕ
2 3nn0 12486 . . . . 5 3 ∈ ℕ0
3 4nn0 12487 . . . . 5 4 ∈ ℕ0
42, 3deccl 12688 . . . 4 34 ∈ ℕ0
5 nnexpcl 14036 . . . 4 ((2 ∈ ℕ ∧ 34 ∈ ℕ0) → (2↑34) ∈ ℕ)
61, 4, 5mp2an 690 . . 3 (2↑34) ∈ ℕ
7 nnm1nn0 12509 . . 3 ((2↑34) ∈ ℕ → ((2↑34) − 1) ∈ ℕ0)
86, 7ax-mp 5 . 2 ((2↑34) − 1) ∈ ℕ0
9 8nn0 12491 . . . 4 8 ∈ ℕ0
10 6nn0 12489 . . . 4 6 ∈ ℕ0
119, 10deccl 12688 . . 3 86 ∈ ℕ0
12 9nn0 12492 . . 3 9 ∈ ℕ0
1311, 12deccl 12688 . 2 869 ∈ ℕ0
14 1259prm.1 . . 3 𝑁 = 1259
15 1nn0 12484 . . . . . 6 1 ∈ ℕ0
16 2nn0 12485 . . . . . 6 2 ∈ ℕ0
1715, 16deccl 12688 . . . . 5 12 ∈ ℕ0
18 5nn0 12488 . . . . 5 5 ∈ ℕ0
1917, 18deccl 12688 . . . 4 125 ∈ ℕ0
20 9nn 12306 . . . 4 9 ∈ ℕ
2119, 20decnncl 12693 . . 3 1259 ∈ ℕ
2214, 21eqeltri 2829 . 2 𝑁 ∈ ℕ
23141259lem2 17061 . . 3 ((2↑34) mod 𝑁) = (870 mod 𝑁)
24 6p1e7 12356 . . . . 5 (6 + 1) = 7
25 eqid 2732 . . . . 5 86 = 86
269, 10, 24, 25decsuc 12704 . . . 4 (86 + 1) = 87
27 eqid 2732 . . . 4 869 = 869
2811, 26, 27decsucc 12714 . . 3 (869 + 1) = 870
2922, 6, 15, 13, 23, 28modsubi 17001 . 2 (((2↑34) − 1) mod 𝑁) = (869 mod 𝑁)
302, 12deccl 12688 . . . 4 39 ∈ ℕ0
31 0nn0 12483 . . . 4 0 ∈ ℕ0
3230, 31deccl 12688 . . 3 390 ∈ ℕ0
339, 12deccl 12688 . . . 4 89 ∈ ℕ0
3416, 15deccl 12688 . . . . . 6 21 ∈ ℕ0
3515, 2deccl 12688 . . . . . . 7 13 ∈ ℕ0
3634nn0zi 12583 . . . . . . . . 9 21 ∈ ℤ
3735nn0zi 12583 . . . . . . . . 9 13 ∈ ℤ
38 gcdcom 16450 . . . . . . . . 9 ((21 ∈ ℤ ∧ 13 ∈ ℤ) → (21 gcd 13) = (13 gcd 21))
3936, 37, 38mp2an 690 . . . . . . . 8 (21 gcd 13) = (13 gcd 21)
40 3nn 12287 . . . . . . . . . . 11 3 ∈ ℕ
4115, 40decnncl 12693 . . . . . . . . . 10 13 ∈ ℕ
42 8nn 12303 . . . . . . . . . 10 8 ∈ ℕ
43 eqid 2732 . . . . . . . . . . 11 13 = 13
449dec0h 12695 . . . . . . . . . . 11 8 = 08
45 ax-1cn 11164 . . . . . . . . . . . . . 14 1 ∈ ℂ
4645mulridi 11214 . . . . . . . . . . . . 13 (1 · 1) = 1
4745addlidi 11398 . . . . . . . . . . . . 13 (0 + 1) = 1
4846, 47oveq12i 7417 . . . . . . . . . . . 12 ((1 · 1) + (0 + 1)) = (1 + 1)
49 1p1e2 12333 . . . . . . . . . . . 12 (1 + 1) = 2
5048, 49eqtri 2760 . . . . . . . . . . 11 ((1 · 1) + (0 + 1)) = 2
51 3cn 12289 . . . . . . . . . . . . . 14 3 ∈ ℂ
5251mulridi 11214 . . . . . . . . . . . . 13 (3 · 1) = 3
5352oveq1i 7415 . . . . . . . . . . . 12 ((3 · 1) + 8) = (3 + 8)
54 8cn 12305 . . . . . . . . . . . . 13 8 ∈ ℂ
55 8p3e11 12754 . . . . . . . . . . . . 13 (8 + 3) = 11
5654, 51, 55addcomli 11402 . . . . . . . . . . . 12 (3 + 8) = 11
5753, 56eqtri 2760 . . . . . . . . . . 11 ((3 · 1) + 8) = 11
5815, 2, 31, 9, 43, 44, 15, 15, 15, 50, 57decmac 12725 . . . . . . . . . 10 ((13 · 1) + 8) = 21
59 1nn 12219 . . . . . . . . . . 11 1 ∈ ℕ
60 8lt10 12805 . . . . . . . . . . 11 8 < 10
6159, 2, 9, 60declti 12711 . . . . . . . . . 10 8 < 13
6241, 15, 42, 58, 61ndvdsi 16351 . . . . . . . . 9 ¬ 13 ∥ 21
63 13prm 17045 . . . . . . . . . 10 13 ∈ ℙ
64 coprm 16644 . . . . . . . . . 10 ((13 ∈ ℙ ∧ 21 ∈ ℤ) → (¬ 13 ∥ 21 ↔ (13 gcd 21) = 1))
6563, 36, 64mp2an 690 . . . . . . . . 9 13 ∥ 21 ↔ (13 gcd 21) = 1)
6662, 65mpbi 229 . . . . . . . 8 (13 gcd 21) = 1
6739, 66eqtri 2760 . . . . . . 7 (21 gcd 13) = 1
68 eqid 2732 . . . . . . . 8 21 = 21
69 2cn 12283 . . . . . . . . . . 11 2 ∈ ℂ
7069mullidi 11215 . . . . . . . . . 10 (1 · 2) = 2
7145addridi 11397 . . . . . . . . . 10 (1 + 0) = 1
7270, 71oveq12i 7417 . . . . . . . . 9 ((1 · 2) + (1 + 0)) = (2 + 1)
73 2p1e3 12350 . . . . . . . . 9 (2 + 1) = 3
7472, 73eqtri 2760 . . . . . . . 8 ((1 · 2) + (1 + 0)) = 3
7546oveq1i 7415 . . . . . . . . 9 ((1 · 1) + 3) = (1 + 3)
76 3p1e4 12353 . . . . . . . . . 10 (3 + 1) = 4
7751, 45, 76addcomli 11402 . . . . . . . . 9 (1 + 3) = 4
783dec0h 12695 . . . . . . . . 9 4 = 04
7975, 77, 783eqtri 2764 . . . . . . . 8 ((1 · 1) + 3) = 04
8016, 15, 15, 2, 68, 43, 15, 3, 31, 74, 79decma2c 12726 . . . . . . 7 ((1 · 21) + 13) = 34
8115, 35, 34, 67, 80gcdi 17002 . . . . . 6 (34 gcd 21) = 1
82 eqid 2732 . . . . . . 7 34 = 34
83 3t2e6 12374 . . . . . . . . . 10 (3 · 2) = 6
8451, 69, 83mulcomli 11219 . . . . . . . . 9 (2 · 3) = 6
8569addridi 11397 . . . . . . . . 9 (2 + 0) = 2
8684, 85oveq12i 7417 . . . . . . . 8 ((2 · 3) + (2 + 0)) = (6 + 2)
87 6p2e8 12367 . . . . . . . 8 (6 + 2) = 8
8886, 87eqtri 2760 . . . . . . 7 ((2 · 3) + (2 + 0)) = 8
89 4cn 12293 . . . . . . . . . 10 4 ∈ ℂ
90 4t2e8 12376 . . . . . . . . . 10 (4 · 2) = 8
9189, 69, 90mulcomli 11219 . . . . . . . . 9 (2 · 4) = 8
9291oveq1i 7415 . . . . . . . 8 ((2 · 4) + 1) = (8 + 1)
93 8p1e9 12358 . . . . . . . 8 (8 + 1) = 9
9412dec0h 12695 . . . . . . . 8 9 = 09
9592, 93, 943eqtri 2764 . . . . . . 7 ((2 · 4) + 1) = 09
962, 3, 16, 15, 82, 68, 16, 12, 31, 88, 95decma2c 12726 . . . . . 6 ((2 · 34) + 21) = 89
9716, 34, 4, 81, 96gcdi 17002 . . . . 5 (89 gcd 34) = 1
98 eqid 2732 . . . . . 6 89 = 89
99 4p3e7 12362 . . . . . . . . 9 (4 + 3) = 7
10089, 51, 99addcomli 11402 . . . . . . . 8 (3 + 4) = 7
101100oveq2i 7416 . . . . . . 7 ((4 · 8) + (3 + 4)) = ((4 · 8) + 7)
102 7nn0 12490 . . . . . . . 8 7 ∈ ℕ0
103 8t4e32 12790 . . . . . . . . 9 (8 · 4) = 32
10454, 89, 103mulcomli 11219 . . . . . . . 8 (4 · 8) = 32
105 7cn 12302 . . . . . . . . 9 7 ∈ ℂ
106 7p2e9 12369 . . . . . . . . 9 (7 + 2) = 9
107105, 69, 106addcomli 11402 . . . . . . . 8 (2 + 7) = 9
1082, 16, 102, 104, 107decaddi 12733 . . . . . . 7 ((4 · 8) + 7) = 39
109101, 108eqtri 2760 . . . . . 6 ((4 · 8) + (3 + 4)) = 39
110 9cn 12308 . . . . . . . 8 9 ∈ ℂ
111 9t4e36 12797 . . . . . . . 8 (9 · 4) = 36
112110, 89, 111mulcomli 11219 . . . . . . 7 (4 · 9) = 36
113 6p4e10 12745 . . . . . . 7 (6 + 4) = 10
1142, 10, 3, 112, 76, 113decaddci2 12735 . . . . . 6 ((4 · 9) + 4) = 40
1159, 12, 2, 3, 98, 82, 3, 31, 3, 109, 114decma2c 12726 . . . . 5 ((4 · 89) + 34) = 390
1163, 4, 33, 97, 115gcdi 17002 . . . 4 (390 gcd 89) = 1
117 eqid 2732 . . . . 5 390 = 390
118 eqid 2732 . . . . . 6 39 = 39
11954addridi 11397 . . . . . . 7 (8 + 0) = 8
120119, 44eqtri 2760 . . . . . 6 (8 + 0) = 08
12169addlidi 11398 . . . . . . . 8 (0 + 2) = 2
12284, 121oveq12i 7417 . . . . . . 7 ((2 · 3) + (0 + 2)) = (6 + 2)
123122, 87eqtri 2760 . . . . . 6 ((2 · 3) + (0 + 2)) = 8
124 9t2e18 12795 . . . . . . . 8 (9 · 2) = 18
125110, 69, 124mulcomli 11219 . . . . . . 7 (2 · 9) = 18
126 8p8e16 12759 . . . . . . 7 (8 + 8) = 16
12715, 9, 9, 125, 49, 10, 126decaddci 12734 . . . . . 6 ((2 · 9) + 8) = 26
1282, 12, 31, 9, 118, 120, 16, 10, 16, 123, 127decma2c 12726 . . . . 5 ((2 · 39) + (8 + 0)) = 86
129 2t0e0 12377 . . . . . . 7 (2 · 0) = 0
130129oveq1i 7415 . . . . . 6 ((2 · 0) + 9) = (0 + 9)
131110addlidi 11398 . . . . . 6 (0 + 9) = 9
132130, 131, 943eqtri 2764 . . . . 5 ((2 · 0) + 9) = 09
13330, 31, 9, 12, 117, 98, 16, 12, 31, 128, 132decma2c 12726 . . . 4 ((2 · 390) + 89) = 869
13416, 33, 32, 116, 133gcdi 17002 . . 3 (869 gcd 390) = 1
13530nn0cni 12480 . . . . . . 7 39 ∈ ℂ
136135addridi 11397 . . . . . 6 (39 + 0) = 39
13754mullidi 11215 . . . . . . . 8 (1 · 8) = 8
138137, 76oveq12i 7417 . . . . . . 7 ((1 · 8) + (3 + 1)) = (8 + 4)
139 8p4e12 12755 . . . . . . 7 (8 + 4) = 12
140138, 139eqtri 2760 . . . . . 6 ((1 · 8) + (3 + 1)) = 12
141 6cn 12299 . . . . . . . . 9 6 ∈ ℂ
142141mullidi 11215 . . . . . . . 8 (1 · 6) = 6
143142oveq1i 7415 . . . . . . 7 ((1 · 6) + 9) = (6 + 9)
144 9p6e15 12764 . . . . . . . 8 (9 + 6) = 15
145110, 141, 144addcomli 11402 . . . . . . 7 (6 + 9) = 15
146143, 145eqtri 2760 . . . . . 6 ((1 · 6) + 9) = 15
1479, 10, 2, 12, 25, 136, 15, 18, 15, 140, 146decma2c 12726 . . . . 5 ((1 · 86) + (39 + 0)) = 125
148110mullidi 11215 . . . . . . 7 (1 · 9) = 9
149148oveq1i 7415 . . . . . 6 ((1 · 9) + 0) = (9 + 0)
150110addridi 11397 . . . . . 6 (9 + 0) = 9
151149, 150, 943eqtri 2764 . . . . 5 ((1 · 9) + 0) = 09
15211, 12, 30, 31, 27, 117, 15, 12, 31, 147, 151decma2c 12726 . . . 4 ((1 · 869) + 390) = 1259
153152, 14eqtr4i 2763 . . 3 ((1 · 869) + 390) = 𝑁
15415, 32, 13, 134, 153gcdi 17002 . 2 (𝑁 gcd 869) = 1
1558, 13, 22, 29, 154gcdmodi 17003 1 (((2↑34) − 1) gcd 𝑁) = 1
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wb 205   = wceq 1541  wcel 2106   class class class wbr 5147  (class class class)co 7405  0cc0 11106  1c1 11107   + caddc 11109   · cmul 11111  cmin 11440  cn 12208  2c2 12263  3c3 12264  4c4 12265  5c5 12266  6c6 12267  7c7 12268  8c8 12269  9c9 12270  0cn0 12468  cz 12554  cdc 12673  cexp 14023  cdvds 16193   gcd cgcd 16431  cprime 16604
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1797  ax-4 1811  ax-5 1913  ax-6 1971  ax-7 2011  ax-8 2108  ax-9 2116  ax-10 2137  ax-11 2154  ax-12 2171  ax-ext 2703  ax-sep 5298  ax-nul 5305  ax-pow 5362  ax-pr 5426  ax-un 7721  ax-cnex 11162  ax-resscn 11163  ax-1cn 11164  ax-icn 11165  ax-addcl 11166  ax-addrcl 11167  ax-mulcl 11168  ax-mulrcl 11169  ax-mulcom 11170  ax-addass 11171  ax-mulass 11172  ax-distr 11173  ax-i2m1 11174  ax-1ne0 11175  ax-1rid 11176  ax-rnegex 11177  ax-rrecex 11178  ax-cnre 11179  ax-pre-lttri 11180  ax-pre-lttrn 11181  ax-pre-ltadd 11182  ax-pre-mulgt0 11183  ax-pre-sup 11184
This theorem depends on definitions:  df-bi 206  df-an 397  df-or 846  df-3or 1088  df-3an 1089  df-tru 1544  df-fal 1554  df-ex 1782  df-nf 1786  df-sb 2068  df-mo 2534  df-eu 2563  df-clab 2710  df-cleq 2724  df-clel 2810  df-nfc 2885  df-ne 2941  df-nel 3047  df-ral 3062  df-rex 3071  df-rmo 3376  df-reu 3377  df-rab 3433  df-v 3476  df-sbc 3777  df-csb 3893  df-dif 3950  df-un 3952  df-in 3954  df-ss 3964  df-pss 3966  df-nul 4322  df-if 4528  df-pw 4603  df-sn 4628  df-pr 4630  df-op 4634  df-uni 4908  df-iun 4998  df-br 5148  df-opab 5210  df-mpt 5231  df-tr 5265  df-id 5573  df-eprel 5579  df-po 5587  df-so 5588  df-fr 5630  df-we 5632  df-xp 5681  df-rel 5682  df-cnv 5683  df-co 5684  df-dm 5685  df-rn 5686  df-res 5687  df-ima 5688  df-pred 6297  df-ord 6364  df-on 6365  df-lim 6366  df-suc 6367  df-iota 6492  df-fun 6542  df-fn 6543  df-f 6544  df-f1 6545  df-fo 6546  df-f1o 6547  df-fv 6548  df-riota 7361  df-ov 7408  df-oprab 7409  df-mpo 7410  df-om 7852  df-1st 7971  df-2nd 7972  df-frecs 8262  df-wrecs 8293  df-recs 8367  df-rdg 8406  df-1o 8462  df-2o 8463  df-er 8699  df-en 8936  df-dom 8937  df-sdom 8938  df-fin 8939  df-sup 9433  df-inf 9434  df-pnf 11246  df-mnf 11247  df-xr 11248  df-ltxr 11249  df-le 11250  df-sub 11442  df-neg 11443  df-div 11868  df-nn 12209  df-2 12271  df-3 12272  df-4 12273  df-5 12274  df-6 12275  df-7 12276  df-8 12277  df-9 12278  df-n0 12469  df-z 12555  df-dec 12674  df-uz 12819  df-rp 12971  df-fz 13481  df-fl 13753  df-mod 13831  df-seq 13963  df-exp 14024  df-cj 15042  df-re 15043  df-im 15044  df-sqrt 15178  df-abs 15179  df-dvds 16194  df-gcd 16432  df-prm 16605
This theorem is referenced by:  1259prm  17065
  Copyright terms: Public domain W3C validator