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

Theorem 1259lem5 16049
Description: Lemma for 1259prm 16050. 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 11458 . . . 4 2 ∈ ℕ
2 3nn0 11573 . . . . 5 3 ∈ ℕ0
3 4nn0 11574 . . . . 5 4 ∈ ℕ0
42, 3deccl 11770 . . . 4 34 ∈ ℕ0
5 nnexpcl 13092 . . . 4 ((2 ∈ ℕ ∧ 34 ∈ ℕ0) → (2↑34) ∈ ℕ)
61, 4, 5mp2an 675 . . 3 (2↑34) ∈ ℕ
7 nnm1nn0 11596 . . 3 ((2↑34) ∈ ℕ → ((2↑34) − 1) ∈ ℕ0)
86, 7ax-mp 5 . 2 ((2↑34) − 1) ∈ ℕ0
9 8nn0 11578 . . . 4 8 ∈ ℕ0
10 6nn0 11576 . . . 4 6 ∈ ℕ0
119, 10deccl 11770 . . 3 86 ∈ ℕ0
12 9nn0 11579 . . 3 9 ∈ ℕ0
1311, 12deccl 11770 . 2 869 ∈ ℕ0
14 1259prm.1 . . 3 𝑁 = 1259
15 1nn0 11571 . . . . . 6 1 ∈ ℕ0
16 2nn0 11572 . . . . . 6 2 ∈ ℕ0
1715, 16deccl 11770 . . . . 5 12 ∈ ℕ0
18 5nn0 11575 . . . . 5 5 ∈ ℕ0
1917, 18deccl 11770 . . . 4 125 ∈ ℕ0
20 9nn 11465 . . . 4 9 ∈ ℕ
2119, 20decnncl 11775 . . 3 1259 ∈ ℕ
2214, 21eqeltri 2881 . 2 𝑁 ∈ ℕ
23141259lem2 16046 . . 3 ((2↑34) mod 𝑁) = (870 mod 𝑁)
24 6p1e7 11435 . . . . 5 (6 + 1) = 7
25 eqid 2806 . . . . 5 86 = 86
269, 10, 24, 25decsuc 11786 . . . 4 (86 + 1) = 87
27 eqid 2806 . . . 4 869 = 869
2811, 26, 27decsucc 11796 . . 3 (869 + 1) = 870
2922, 6, 15, 13, 23, 28modsubi 15989 . 2 (((2↑34) − 1) mod 𝑁) = (869 mod 𝑁)
302, 12deccl 11770 . . . 4 39 ∈ ℕ0
31 0nn0 11570 . . . 4 0 ∈ ℕ0
3230, 31deccl 11770 . . 3 390 ∈ ℕ0
339, 12deccl 11770 . . . 4 89 ∈ ℕ0
3416, 15deccl 11770 . . . . . 6 21 ∈ ℕ0
3515, 2deccl 11770 . . . . . . 7 13 ∈ ℕ0
3634nn0zi 11664 . . . . . . . . 9 21 ∈ ℤ
3735nn0zi 11664 . . . . . . . . 9 13 ∈ ℤ
38 gcdcom 15450 . . . . . . . . 9 ((21 ∈ ℤ ∧ 13 ∈ ℤ) → (21 gcd 13) = (13 gcd 21))
3936, 37, 38mp2an 675 . . . . . . . 8 (21 gcd 13) = (13 gcd 21)
40 3nn 11459 . . . . . . . . . . 11 3 ∈ ℕ
4115, 40decnncl 11775 . . . . . . . . . 10 13 ∈ ℕ
42 8nn 11464 . . . . . . . . . 10 8 ∈ ℕ
43 eqid 2806 . . . . . . . . . . 11 13 = 13
449dec0h 11777 . . . . . . . . . . 11 8 = 08
45 ax-1cn 10275 . . . . . . . . . . . . . 14 1 ∈ ℂ
4645mulid1i 10325 . . . . . . . . . . . . 13 (1 · 1) = 1
4745addid2i 10505 . . . . . . . . . . . . 13 (0 + 1) = 1
4846, 47oveq12i 6882 . . . . . . . . . . . 12 ((1 · 1) + (0 + 1)) = (1 + 1)
49 1p1e2 11413 . . . . . . . . . . . 12 (1 + 1) = 2
5048, 49eqtri 2828 . . . . . . . . . . 11 ((1 · 1) + (0 + 1)) = 2
51 3cn 11375 . . . . . . . . . . . . . 14 3 ∈ ℂ
5251mulid1i 10325 . . . . . . . . . . . . 13 (3 · 1) = 3
5352oveq1i 6880 . . . . . . . . . . . 12 ((3 · 1) + 8) = (3 + 8)
54 8cn 11386 . . . . . . . . . . . . 13 8 ∈ ℂ
55 8p3e11 11836 . . . . . . . . . . . . 13 (8 + 3) = 11
5654, 51, 55addcomli 10509 . . . . . . . . . . . 12 (3 + 8) = 11
5753, 56eqtri 2828 . . . . . . . . . . 11 ((3 · 1) + 8) = 11
5815, 2, 31, 9, 43, 44, 15, 15, 15, 50, 57decmac 11807 . . . . . . . . . 10 ((13 · 1) + 8) = 21
59 1nn 11312 . . . . . . . . . . 11 1 ∈ ℕ
60 8lt10 11887 . . . . . . . . . . 11 8 < 10
6159, 2, 9, 60declti 11793 . . . . . . . . . 10 8 < 13
6241, 15, 42, 58, 61ndvdsi 15351 . . . . . . . . 9 ¬ 13 ∥ 21
63 13prm 16030 . . . . . . . . . 10 13 ∈ ℙ
64 coprm 15636 . . . . . . . . . 10 ((13 ∈ ℙ ∧ 21 ∈ ℤ) → (¬ 13 ∥ 21 ↔ (13 gcd 21) = 1))
6563, 36, 64mp2an 675 . . . . . . . . 9 13 ∥ 21 ↔ (13 gcd 21) = 1)
6662, 65mpbi 221 . . . . . . . 8 (13 gcd 21) = 1
6739, 66eqtri 2828 . . . . . . 7 (21 gcd 13) = 1
68 eqid 2806 . . . . . . . 8 21 = 21
69 2cn 11371 . . . . . . . . . . 11 2 ∈ ℂ
7069mulid2i 10326 . . . . . . . . . 10 (1 · 2) = 2
7145addid1i 10504 . . . . . . . . . 10 (1 + 0) = 1
7270, 71oveq12i 6882 . . . . . . . . 9 ((1 · 2) + (1 + 0)) = (2 + 1)
73 2p1e3 11430 . . . . . . . . 9 (2 + 1) = 3
7472, 73eqtri 2828 . . . . . . . 8 ((1 · 2) + (1 + 0)) = 3
7546oveq1i 6880 . . . . . . . . 9 ((1 · 1) + 3) = (1 + 3)
76 3p1e4 11432 . . . . . . . . . 10 (3 + 1) = 4
7751, 45, 76addcomli 10509 . . . . . . . . 9 (1 + 3) = 4
783dec0h 11777 . . . . . . . . 9 4 = 04
7975, 77, 783eqtri 2832 . . . . . . . 8 ((1 · 1) + 3) = 04
8016, 15, 15, 2, 68, 43, 15, 3, 31, 74, 79decma2c 11808 . . . . . . 7 ((1 · 21) + 13) = 34
8115, 35, 34, 67, 80gcdi 15990 . . . . . 6 (34 gcd 21) = 1
82 eqid 2806 . . . . . . 7 34 = 34
83 3t2e6 11453 . . . . . . . . . 10 (3 · 2) = 6
8451, 69, 83mulcomli 10330 . . . . . . . . 9 (2 · 3) = 6
8569addid1i 10504 . . . . . . . . 9 (2 + 0) = 2
8684, 85oveq12i 6882 . . . . . . . 8 ((2 · 3) + (2 + 0)) = (6 + 2)
87 6p2e8 11446 . . . . . . . 8 (6 + 2) = 8
8886, 87eqtri 2828 . . . . . . 7 ((2 · 3) + (2 + 0)) = 8
89 4cn 11378 . . . . . . . . . 10 4 ∈ ℂ
90 4t2e8 11455 . . . . . . . . . 10 (4 · 2) = 8
9189, 69, 90mulcomli 10330 . . . . . . . . 9 (2 · 4) = 8
9291oveq1i 6880 . . . . . . . 8 ((2 · 4) + 1) = (8 + 1)
93 8p1e9 11437 . . . . . . . 8 (8 + 1) = 9
9412dec0h 11777 . . . . . . . 8 9 = 09
9592, 93, 943eqtri 2832 . . . . . . 7 ((2 · 4) + 1) = 09
962, 3, 16, 15, 82, 68, 16, 12, 31, 88, 95decma2c 11808 . . . . . 6 ((2 · 34) + 21) = 89
9716, 34, 4, 81, 96gcdi 15990 . . . . 5 (89 gcd 34) = 1
98 eqid 2806 . . . . . 6 89 = 89
99 4p3e7 11441 . . . . . . . . 9 (4 + 3) = 7
10089, 51, 99addcomli 10509 . . . . . . . 8 (3 + 4) = 7
101100oveq2i 6881 . . . . . . 7 ((4 · 8) + (3 + 4)) = ((4 · 8) + 7)
102 7nn0 11577 . . . . . . . 8 7 ∈ ℕ0
103 8t4e32 11872 . . . . . . . . 9 (8 · 4) = 32
10454, 89, 103mulcomli 10330 . . . . . . . 8 (4 · 8) = 32
105 7cn 11384 . . . . . . . . 9 7 ∈ ℂ
106 7p2e9 11448 . . . . . . . . 9 (7 + 2) = 9
107105, 69, 106addcomli 10509 . . . . . . . 8 (2 + 7) = 9
1082, 16, 102, 104, 107decaddi 11815 . . . . . . 7 ((4 · 8) + 7) = 39
109101, 108eqtri 2828 . . . . . 6 ((4 · 8) + (3 + 4)) = 39
110 9cn 11388 . . . . . . . 8 9 ∈ ℂ
111 9t4e36 11879 . . . . . . . 8 (9 · 4) = 36
112110, 89, 111mulcomli 10330 . . . . . . 7 (4 · 9) = 36
113 6p4e10 11827 . . . . . . 7 (6 + 4) = 10
1142, 10, 3, 112, 76, 113decaddci2 11817 . . . . . 6 ((4 · 9) + 4) = 40
1159, 12, 2, 3, 98, 82, 3, 31, 3, 109, 114decma2c 11808 . . . . 5 ((4 · 89) + 34) = 390
1163, 4, 33, 97, 115gcdi 15990 . . . 4 (390 gcd 89) = 1
117 eqid 2806 . . . . 5 390 = 390
118 eqid 2806 . . . . . 6 39 = 39
11954addid1i 10504 . . . . . . 7 (8 + 0) = 8
120119, 44eqtri 2828 . . . . . 6 (8 + 0) = 08
12169addid2i 10505 . . . . . . . 8 (0 + 2) = 2
12284, 121oveq12i 6882 . . . . . . 7 ((2 · 3) + (0 + 2)) = (6 + 2)
123122, 87eqtri 2828 . . . . . 6 ((2 · 3) + (0 + 2)) = 8
124 9t2e18 11877 . . . . . . . 8 (9 · 2) = 18
125110, 69, 124mulcomli 10330 . . . . . . 7 (2 · 9) = 18
126 8p8e16 11841 . . . . . . 7 (8 + 8) = 16
12715, 9, 9, 125, 49, 10, 126decaddci 11816 . . . . . 6 ((2 · 9) + 8) = 26
1282, 12, 31, 9, 118, 120, 16, 10, 16, 123, 127decma2c 11808 . . . . 5 ((2 · 39) + (8 + 0)) = 86
129 2t0e0 11456 . . . . . . 7 (2 · 0) = 0
130129oveq1i 6880 . . . . . 6 ((2 · 0) + 9) = (0 + 9)
131110addid2i 10505 . . . . . 6 (0 + 9) = 9
132130, 131, 943eqtri 2832 . . . . 5 ((2 · 0) + 9) = 09
13330, 31, 9, 12, 117, 98, 16, 12, 31, 128, 132decma2c 11808 . . . 4 ((2 · 390) + 89) = 869
13416, 33, 32, 116, 133gcdi 15990 . . 3 (869 gcd 390) = 1
13530nn0cni 11567 . . . . . . 7 39 ∈ ℂ
136135addid1i 10504 . . . . . 6 (39 + 0) = 39
13754mulid2i 10326 . . . . . . . 8 (1 · 8) = 8
138137, 76oveq12i 6882 . . . . . . 7 ((1 · 8) + (3 + 1)) = (8 + 4)
139 8p4e12 11837 . . . . . . 7 (8 + 4) = 12
140138, 139eqtri 2828 . . . . . 6 ((1 · 8) + (3 + 1)) = 12
141 6cn 11382 . . . . . . . . 9 6 ∈ ℂ
142141mulid2i 10326 . . . . . . . 8 (1 · 6) = 6
143142oveq1i 6880 . . . . . . 7 ((1 · 6) + 9) = (6 + 9)
144 9p6e15 11846 . . . . . . . 8 (9 + 6) = 15
145110, 141, 144addcomli 10509 . . . . . . 7 (6 + 9) = 15
146143, 145eqtri 2828 . . . . . 6 ((1 · 6) + 9) = 15
1479, 10, 2, 12, 25, 136, 15, 18, 15, 140, 146decma2c 11808 . . . . 5 ((1 · 86) + (39 + 0)) = 125
148110mulid2i 10326 . . . . . . 7 (1 · 9) = 9
149148oveq1i 6880 . . . . . 6 ((1 · 9) + 0) = (9 + 0)
150110addid1i 10504 . . . . . 6 (9 + 0) = 9
151149, 150, 943eqtri 2832 . . . . 5 ((1 · 9) + 0) = 09
15211, 12, 30, 31, 27, 117, 15, 12, 31, 147, 151decma2c 11808 . . . 4 ((1 · 869) + 390) = 1259
153152, 14eqtr4i 2831 . . 3 ((1 · 869) + 390) = 𝑁
15415, 32, 13, 134, 153gcdi 15990 . 2 (𝑁 gcd 869) = 1
1558, 13, 22, 29, 154gcdmodi 15991 1 (((2↑34) − 1) gcd 𝑁) = 1
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wb 197   = wceq 1637  wcel 2156   class class class wbr 4844  (class class class)co 6870  0cc0 10217  1c1 10218   + caddc 10220   · cmul 10222  cmin 10547  cn 11301  2c2 11352  3c3 11353  4c4 11354  5c5 11355  6c6 11356  7c7 11357  8c8 11358  9c9 11359  0cn0 11555  cz 11639  cdc 11755  cexp 13079  cdvds 15199   gcd cgcd 15431  cprime 15599
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 2068  ax-7 2104  ax-8 2158  ax-9 2165  ax-10 2185  ax-11 2201  ax-12 2214  ax-13 2420  ax-ext 2784  ax-sep 4975  ax-nul 4983  ax-pow 5035  ax-pr 5096  ax-un 7175  ax-cnex 10273  ax-resscn 10274  ax-1cn 10275  ax-icn 10276  ax-addcl 10277  ax-addrcl 10278  ax-mulcl 10279  ax-mulrcl 10280  ax-mulcom 10281  ax-addass 10282  ax-mulass 10283  ax-distr 10284  ax-i2m1 10285  ax-1ne0 10286  ax-1rid 10287  ax-rnegex 10288  ax-rrecex 10289  ax-cnre 10290  ax-pre-lttri 10291  ax-pre-lttrn 10292  ax-pre-ltadd 10293  ax-pre-mulgt0 10294  ax-pre-sup 10295
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 2061  df-eu 2634  df-mo 2635  df-clab 2793  df-cleq 2799  df-clel 2802  df-nfc 2937  df-ne 2979  df-nel 3082  df-ral 3101  df-rex 3102  df-reu 3103  df-rmo 3104  df-rab 3105  df-v 3393  df-sbc 3634  df-csb 3729  df-dif 3772  df-un 3774  df-in 3776  df-ss 3783  df-pss 3785  df-nul 4117  df-if 4280  df-pw 4353  df-sn 4371  df-pr 4373  df-tp 4375  df-op 4377  df-uni 4631  df-iun 4714  df-br 4845  df-opab 4907  df-mpt 4924  df-tr 4947  df-id 5219  df-eprel 5224  df-po 5232  df-so 5233  df-fr 5270  df-we 5272  df-xp 5317  df-rel 5318  df-cnv 5319  df-co 5320  df-dm 5321  df-rn 5322  df-res 5323  df-ima 5324  df-pred 5893  df-ord 5939  df-on 5940  df-lim 5941  df-suc 5942  df-iota 6060  df-fun 6099  df-fn 6100  df-f 6101  df-f1 6102  df-fo 6103  df-f1o 6104  df-fv 6105  df-riota 6831  df-ov 6873  df-oprab 6874  df-mpt2 6875  df-om 7292  df-1st 7394  df-2nd 7395  df-wrecs 7638  df-recs 7700  df-rdg 7738  df-1o 7792  df-2o 7793  df-er 7975  df-en 8189  df-dom 8190  df-sdom 8191  df-fin 8192  df-sup 8583  df-inf 8584  df-pnf 10357  df-mnf 10358  df-xr 10359  df-ltxr 10360  df-le 10361  df-sub 10549  df-neg 10550  df-div 10966  df-nn 11302  df-2 11360  df-3 11361  df-4 11362  df-5 11363  df-6 11364  df-7 11365  df-8 11366  df-9 11367  df-n0 11556  df-z 11640  df-dec 11756  df-uz 11901  df-rp 12043  df-fz 12546  df-fl 12813  df-mod 12889  df-seq 13021  df-exp 13080  df-cj 14058  df-re 14059  df-im 14060  df-sqrt 14194  df-abs 14195  df-dvds 15200  df-gcd 15432  df-prm 15600
This theorem is referenced by:  1259prm  16050
  Copyright terms: Public domain W3C validator