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

Theorem 4001lem3 17365
Description: Lemma for 4001prm 17367. Calculate a power mod. In decimal, we calculate 2↑1000 = 2↑800 · 2↑200≡2311 · 902 = 521𝑁 + 1 and finally 2↑(𝑁 − 1) = (2↑1000)↑4≡1↑4 = 1. (Contributed by Mario Carneiro, 3-Mar-2014.) (Revised by Mario Carneiro, 20-Apr-2015.) (Proof shortened by AV, 16-Sep-2021.)
Hypothesis
Ref Expression
4001prm.1 𝑁 = 4001
Assertion
Ref Expression
4001lem3 ((2↑(𝑁 − 1)) mod 𝑁) = (1 mod 𝑁)

Proof of Theorem 4001lem3
StepHypRef Expression
1 4001prm.1 . . 3 𝑁 = 4001
2 4nn0 12665 . . . . . 6 4 ∈ ℕ0
3 0nn0 12661 . . . . . 6 0 ∈ ℕ0
42, 3deccl 12869 . . . . 5 40 ∈ ℕ0
54, 3deccl 12869 . . . 4 400 ∈ ℕ0
6 1nn 12386 . . . 4 1 ∈ ℕ
75, 6decnncl 12878 . . 3 4001 ∈ ℕ
81, 7eqeltri 2860 . 2 𝑁 ∈ ℕ
9 2nn 12456 . 2 2 ∈ ℕ
10 2nn0 12663 . . . . 5 2 ∈ ℕ0
1110, 3deccl 12869 . . . 4 20 ∈ ℕ0
1211, 3deccl 12869 . . 3 200 ∈ ℕ0
1312, 3deccl 12869 . 2 2000 ∈ ℕ0
14 0z 12744 . 2 0 ∈ ℤ
15 1nn0 12662 . 2 1 ∈ ℕ0
16 10nn0 12876 . . . . 5 10 ∈ ℕ0
1716, 3deccl 12869 . . . 4 100 ∈ ℕ0
1817, 3deccl 12869 . . 3 1000 ∈ ℕ0
19 8nn0 12669 . . . . . 6 8 ∈ ℕ0
2019, 3deccl 12869 . . . . 5 80 ∈ ℕ0
2120, 3deccl 12869 . . . 4 800 ∈ ℕ0
22 5nn0 12666 . . . . . . 7 5 ∈ ℕ0
2322, 10deccl 12869 . . . . . 6 52 ∈ ℕ0
2423, 15deccl 12869 . . . . 5 521 ∈ ℕ0
2524nn0zi 12761 . . . 4 521 ∈ ℤ
26 3nn0 12664 . . . . . . 7 3 ∈ ℕ0
2710, 26deccl 12869 . . . . . 6 23 ∈ ℕ0
2827, 15deccl 12869 . . . . 5 231 ∈ ℕ0
2928, 15deccl 12869 . . . 4 2311 ∈ ℕ0
30 9nn0 12670 . . . . . 6 9 ∈ ℕ0
3130, 3deccl 12869 . . . . 5 90 ∈ ℕ0
3231, 10deccl 12869 . . . 4 902 ∈ ℕ0
3314001lem2 17364 . . . 4 ((2↑800) mod 𝑁) = (2311 mod 𝑁)
3414001lem1 17363 . . . 4 ((2↑200) mod 𝑁) = (902 mod 𝑁)
35 eqid 2763 . . . . 5 800 = 800
36 eqid 2763 . . . . 5 200 = 200
37 eqid 2763 . . . . . 6 80 = 80
38 eqid 2763 . . . . . 6 20 = 20
39 8p2e10 12939 . . . . . 6 (8 + 2) = 10
40 00id 11524 . . . . . 6 (0 + 0) = 0
4119, 3, 10, 3, 37, 38, 39, 40decadd 12913 . . . . 5 (80 + 20) = 100
4220, 3, 11, 3, 35, 36, 41, 40decadd 12913 . . . 4 (800 + 200) = 1000
4315dec0h 12881 . . . . . 6 1 = 01
44 eqid 2763 . . . . . . 7 400 = 400
4523nn0cni 12658 . . . . . . . 8 52 ∈ ℂ
4645addlidi 11537 . . . . . . 7 (0 + 52) = 52
47 eqid 2763 . . . . . . . 8 40 = 40
48 5cn 12471 . . . . . . . . . 10 5 ∈ ℂ
4948addridi 11536 . . . . . . . . 9 (5 + 0) = 5
5022dec0h 12881 . . . . . . . . 9 5 = 05
5149, 50eqtri 2786 . . . . . . . 8 (5 + 0) = 05
5240, 3eqeltri 2860 . . . . . . . . 9 (0 + 0) ∈ ℕ0
53 eqid 2763 . . . . . . . . 9 521 = 521
54 eqid 2763 . . . . . . . . . 10 52 = 52
55 5t4e20 12961 . . . . . . . . . 10 (5 · 4) = 20
56 2t4e8 12552 . . . . . . . . . 10 (2 · 4) = 8
572, 22, 10, 54, 55, 56decmul1 12923 . . . . . . . . 9 (52 · 4) = 208
58 4cn 12468 . . . . . . . . . . . 12 4 ∈ ℂ
5958mullidi 11353 . . . . . . . . . . 11 (1 · 4) = 4
6059, 40oveq12i 7463 . . . . . . . . . 10 ((1 · 4) + (0 + 0)) = (4 + 0)
6158addridi 11536 . . . . . . . . . 10 (4 + 0) = 4
6260, 61eqtri 2786 . . . . . . . . 9 ((1 · 4) + (0 + 0)) = 4
6323, 15, 52, 53, 2, 57, 62decrmanc 12916 . . . . . . . 8 ((521 · 4) + (0 + 0)) = 2084
6424nn0cni 12658 . . . . . . . . . . 11 521 ∈ ℂ
6564mul01i 11539 . . . . . . . . . 10 (521 · 0) = 0
6665oveq1i 7461 . . . . . . . . 9 ((521 · 0) + 5) = (0 + 5)
6748addlidi 11537 . . . . . . . . 9 (0 + 5) = 5
6866, 67, 503eqtri 2790 . . . . . . . 8 ((521 · 0) + 5) = 05
692, 3, 3, 22, 47, 51, 24, 22, 3, 63, 68decma2c 12912 . . . . . . 7 ((521 · 40) + (5 + 0)) = 20845
7065oveq1i 7461 . . . . . . . 8 ((521 · 0) + 2) = (0 + 2)
71 2cn 12458 . . . . . . . . 9 2 ∈ ℂ
7271addlidi 11537 . . . . . . . 8 (0 + 2) = 2
7310dec0h 12881 . . . . . . . 8 2 = 02
7470, 72, 733eqtri 2790 . . . . . . 7 ((521 · 0) + 2) = 02
754, 3, 22, 10, 44, 46, 24, 10, 3, 69, 74decma2c 12912 . . . . . 6 ((521 · 400) + (0 + 52)) = 208452
7645mulridi 11352 . . . . . . 7 (52 · 1) = 52
77 ax-1cn 11297 . . . . . . . . . 10 1 ∈ ℂ
7877mullidi 11353 . . . . . . . . 9 (1 · 1) = 1
7978oveq1i 7461 . . . . . . . 8 ((1 · 1) + 1) = (1 + 1)
80 1p1e2 12506 . . . . . . . 8 (1 + 1) = 2
8179, 80eqtri 2786 . . . . . . 7 ((1 · 1) + 1) = 2
8223, 15, 15, 53, 15, 76, 81decrmanc 12916 . . . . . 6 ((521 · 1) + 1) = 522
835, 15, 3, 15, 1, 43, 24, 10, 23, 75, 82decma2c 12912 . . . . 5 ((521 · 𝑁) + 1) = 2084522
84 eqid 2763 . . . . . 6 902 = 902
85 6nn0 12667 . . . . . . . 8 6 ∈ ℕ0
862, 85deccl 12869 . . . . . . 7 46 ∈ ℕ0
8786, 10deccl 12869 . . . . . 6 462 ∈ ℕ0
88 eqid 2763 . . . . . . 7 90 = 90
89 eqid 2763 . . . . . . 7 462 = 462
90 eqid 2763 . . . . . . . 8 2311 = 2311
9186nn0cni 12658 . . . . . . . . 9 46 ∈ ℂ
9291addridi 11536 . . . . . . . 8 (46 + 0) = 46
93 4p1e5 12528 . . . . . . . . . 10 (4 + 1) = 5
9493, 22eqeltri 2860 . . . . . . . . 9 (4 + 1) ∈ ℕ0
95 eqid 2763 . . . . . . . . 9 231 = 231
96 eqid 2763 . . . . . . . . . 10 23 = 23
97 9cn 12483 . . . . . . . . . . . 12 9 ∈ ℂ
98 9t2e18 12981 . . . . . . . . . . . 12 (9 · 2) = 18
9997, 71, 98mulcomli 11357 . . . . . . . . . . 11 (2 · 9) = 18
10015, 19, 10, 99, 80, 39decaddci2 12921 . . . . . . . . . 10 ((2 · 9) + 2) = 20
101 7nn0 12668 . . . . . . . . . . 11 7 ∈ ℕ0
102 7p1e8 12531 . . . . . . . . . . 11 (7 + 1) = 8
103 3cn 12464 . . . . . . . . . . . 12 3 ∈ ℂ
104 9t3e27 12982 . . . . . . . . . . . 12 (9 · 3) = 27
10597, 103, 104mulcomli 11357 . . . . . . . . . . 11 (3 · 9) = 27
10610, 101, 102, 105decsuc 12890 . . . . . . . . . 10 ((3 · 9) + 1) = 28
10710, 26, 15, 96, 30, 19, 10, 100, 106decrmac 12917 . . . . . . . . 9 ((23 · 9) + 1) = 208
10897mullidi 11353 . . . . . . . . . . 11 (1 · 9) = 9
109108, 93oveq12i 7463 . . . . . . . . . 10 ((1 · 9) + (4 + 1)) = (9 + 5)
110 9p5e14 12949 . . . . . . . . . 10 (9 + 5) = 14
111109, 110eqtri 2786 . . . . . . . . 9 ((1 · 9) + (4 + 1)) = 14
11227, 15, 94, 95, 30, 2, 15, 107, 111decrmac 12917 . . . . . . . 8 ((231 · 9) + (4 + 1)) = 2084
113108oveq1i 7461 . . . . . . . . 9 ((1 · 9) + 6) = (9 + 6)
114 9p6e15 12950 . . . . . . . . 9 (9 + 6) = 15
115113, 114eqtri 2786 . . . . . . . 8 ((1 · 9) + 6) = 15
11628, 15, 2, 85, 90, 92, 30, 22, 15, 112, 115decmac 12911 . . . . . . 7 ((2311 · 9) + (46 + 0)) = 20845
11729nn0cni 12658 . . . . . . . . . 10 2311 ∈ ℂ
118117mul01i 11539 . . . . . . . . 9 (2311 · 0) = 0
119118oveq1i 7461 . . . . . . . 8 ((2311 · 0) + 2) = (0 + 2)
120119, 72, 733eqtri 2790 . . . . . . 7 ((2311 · 0) + 2) = 02
12130, 3, 86, 10, 88, 89, 29, 10, 3, 116, 120decma2c 12912 . . . . . 6 ((2311 · 90) + 462) = 208452
122 2t2e4 12546 . . . . . . . . 9 (2 · 2) = 4
123 3t2e6 12548 . . . . . . . . 9 (3 · 2) = 6
12410, 10, 26, 96, 122, 123decmul1 12923 . . . . . . . 8 (23 · 2) = 46
12571mullidi 11353 . . . . . . . 8 (1 · 2) = 2
12610, 27, 15, 95, 124, 125decmul1 12923 . . . . . . 7 (231 · 2) = 462
12710, 28, 15, 90, 126, 125decmul1 12923 . . . . . 6 (2311 · 2) = 4622
12829, 31, 10, 84, 10, 87, 121, 127decmul2c 12925 . . . . 5 (2311 · 902) = 2084522
12983, 128eqtr4i 2789 . . . 4 ((521 · 𝑁) + 1) = (2311 · 902)
1308, 9, 21, 25, 29, 15, 12, 32, 33, 34, 42, 129modxai 17290 . . 3 ((2↑1000) mod 𝑁) = (1 mod 𝑁)
13118nn0cni 12658 . . . 4 1000 ∈ ℂ
132 eqid 2763 . . . . 5 1000 = 1000
133 eqid 2763 . . . . . 6 100 = 100
13410dec0u 12880 . . . . . 6 (10 · 2) = 20
13571mul02i 11538 . . . . . 6 (0 · 2) = 0
13610, 16, 3, 133, 134, 135decmul1 12923 . . . . 5 (100 · 2) = 200
13710, 17, 3, 132, 136, 135decmul1 12923 . . . 4 (1000 · 2) = 2000
138131, 71, 137mulcomli 11357 . . 3 (2 · 1000) = 2000
1398nncni 12385 . . . . . 6 𝑁 ∈ ℂ
140139mul02i 11538 . . . . 5 (0 · 𝑁) = 0
141140oveq1i 7461 . . . 4 ((0 · 𝑁) + 1) = (0 + 1)
14277addlidi 11537 . . . . 5 (0 + 1) = 1
14378, 142eqtr4i 2789 . . . 4 (1 · 1) = (0 + 1)
144141, 143eqtr4i 2789 . . 3 ((0 · 𝑁) + 1) = (1 · 1)
1458, 9, 18, 14, 15, 15, 130, 138, 144mod2xi 17291 . 2 ((2↑2000) mod 𝑁) = (1 mod 𝑁)
14613nn0cni 12658 . . . 4 2000 ∈ ℂ
147 eqid 2763 . . . . 5 2000 = 2000
14810, 10, 3, 38, 122, 135decmul1 12923 . . . . . 6 (20 · 2) = 40
14910, 11, 3, 36, 148, 135decmul1 12923 . . . . 5 (200 · 2) = 400
15010, 12, 3, 147, 149, 135decmul1 12923 . . . 4 (2000 · 2) = 4000
151146, 71, 150mulcomli 11357 . . 3 (2 · 2000) = 4000
1525, 3deccl 12869 . . . . 5 4000 ∈ ℕ0
153152nn0cni 12658 . . . 4 4000 ∈ ℂ
154 eqid 2763 . . . . . 6 4000 = 4000
1555, 3, 142, 154decsuc 12890 . . . . 5 (4000 + 1) = 4001
1561, 155eqtr4i 2789 . . . 4 𝑁 = (4000 + 1)
157153, 77, 156mvrraddi 11613 . . 3 (𝑁 − 1) = 4000
158151, 157eqtr4i 2789 . 2 (2 · 2000) = (𝑁 − 1)
1598, 9, 13, 14, 15, 15, 145, 158, 144mod2xi 17291 1 ((2↑(𝑁 − 1)) mod 𝑁) = (1 mod 𝑁)
Colors of variables:    wff setvar class
This proof depends on syntax axioms:   = wceq 1570  (class class class)co 7451  0cc0 11239  1c1 11240   + caddc 11242   · cmul 11244   − cmin 11580  ℕcn 12375  2c2 12437  3c3 12438  4c4 12439  5c5 12440  6c6 12441  7c7 12442  8c8 12443  9c9 12444  ℕ0cn0 12646  cdc 12854   mod cmo 14049  ↑cexp 14244
This proof depends on axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1828  ax-4 1842  ax-5 1945  ax-6 2002  ax-7 2043  ax-8 2149  ax-9 2157  ax-10 2180  ax-11 2197  ax-12 2216  ax-ext 2735  ax-sep 5255  ax-nul 5266  ax-pow 5334  ax-pr 5398  ax-un 7783  ax-cnex 11295  ax-resscn 11296  ax-1cn 11297  ax-icn 11298  ax-addcl 11299  ax-addrcl 11300  ax-mulcl 11301  ax-mulrcl 11302  ax-mulcom 11303  ax-addass 11304  ax-mulass 11305  ax-distr 11306  ax-i2m1 11307  ax-1ne0 11308  ax-1rid 11309  ax-rnegex 11310  ax-rrecex 11311  ax-cnre 11312  ax-pre-lttri 11313  ax-pre-lttrn 11314  ax-pre-ltadd 11315  ax-pre-mulgt0 11316  ax-pre-sup 11317
This proof depends on definitions:  df-bi 210  df-an 402  df-or 862  df-3or 1104  df-3an 1105  df-tru 1573  df-fal 1583  df-ex 1813  df-nf 1817  df-sb 2102  df-mo 2567  df-eu 2597  df-clab 2742  df-cleq 2755  df-clel 2839  df-nfc 2913  df-ne 2960  df-nel 3066  df-ral 3081  df-rex 3091  df-rmo 3369  df-reu 3370  df-rab 3417  df-v 3456  df-sbc 3743  df-csb 3852  df-ss 3901  df-pss 4017  df-dif 4050  df-in 4094  df-un 4154  df-nul 4282  df-if 4486  df-pw 4562  df-sn 4589  df-pr 4591  df-op 4841  df-uni 4873  df-iun 4958  df-br 5109  df-opab 5174  df-mpt 5193  df-tr 5219  df-id 5553  df-eprel 5558  df-po 5566  df-so 5567  df-fr 5611  df-we 5613  df-xp 5664  df-rel 5665  df-cnv 5666  df-co 5667  df-dm 5668  df-rn 5669  df-res 5670  df-ima 5671  df-pred 6330  df-ord 6391  df-on 6392  df-lim 6393  df-suc 6394  df-iota 6520  df-fun 6568  df-fn 6569  df-f 6570  df-f1 6571  df-fo 6572  df-f1o 6573  df-fv 6574  df-riota 7408  df-ov 7454  df-oprab 7455  df-mpo 7456  df-om 7912  df-2nd 8036  df-frecs 8337  df-wrecs 8368  df-recs 8417  df-rdg 8456  df-er 8755  df-en 9012  df-dom 9013  df-sdom 9014  df-sup 9471  df-inf 9472  df-pnf 11384  df-mnf 11385  df-xr 11386  df-ltxr 11387  df-le 11388  df-sub 11582  df-neg 11583  df-div 12014  df-nn 12376  df-2 12445  df-3 12446  df-4 12447  df-5 12448  df-6 12449  df-7 12450  df-8 12451  df-9 12452  df-n0 12647  df-z 12734  df-dec 12855  df-uz 13006  df-rp 13161  df-fl 13972  df-mod 14050  df-seq 14185  df-exp 14245
This theorem is used by:  4001prm  17367
  Copyright terms: Public domain W3C validator