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

Theorem 4001prm 16083
Description: 4001 is a prime number. (Contributed by Mario Carneiro, 3-Mar-2014.) (Proof shortened by Mario Carneiro, 20-Apr-2015.) (Proof shortened by AV, 16-Sep-2021.)
Hypothesis
Ref Expression
4001prm.1 𝑁 = 4001
Assertion
Ref Expression
4001prm 𝑁 ∈ ℙ

Proof of Theorem 4001prm
StepHypRef Expression
1 5prm 16047 . 2 5 ∈ ℙ
2 8nn 11413 . . . 4 8 ∈ ℕ
32decnncl2 11803 . . 3 80 ∈ ℕ
43decnncl2 11803 . 2 800 ∈ ℕ
5 4nn0 11598 . . . . . . . 8 4 ∈ ℕ0
6 0nn0 11594 . . . . . . . 8 0 ∈ ℕ0
75, 6deccl 11794 . . . . . . 7 40 ∈ ℕ0
87, 6deccl 11794 . . . . . 6 400 ∈ ℕ0
98, 6deccl 11794 . . . . 5 4000 ∈ ℕ0
109nn0cni 11591 . . . 4 4000 ∈ ℂ
11 ax-1cn 10289 . . . 4 1 ∈ ℂ
12 4001prm.1 . . . . 5 𝑁 = 4001
1311addid2i 10519 . . . . . 6 (0 + 1) = 1
14 eqid 2817 . . . . . 6 4000 = 4000
158, 6, 13, 14decsuc 11810 . . . . 5 (4000 + 1) = 4001
1612, 15eqtr4i 2842 . . . 4 𝑁 = (4000 + 1)
1710, 11, 16mvrraddi 10593 . . 3 (𝑁 − 1) = 4000
18 5nn0 11599 . . . 4 5 ∈ ℕ0
19 8nn0 11602 . . . . 5 8 ∈ ℕ0
2019, 6deccl 11794 . . . 4 80 ∈ ℕ0
21 eqid 2817 . . . 4 800 = 800
22 eqid 2817 . . . . 5 80 = 80
23 8t5e40 11897 . . . . 5 (8 · 5) = 40
24 5cn 11403 . . . . . 6 5 ∈ ℂ
2524mul02i 10520 . . . . 5 (0 · 5) = 0
2618, 19, 6, 22, 6, 23, 25decmul1 11843 . . . 4 (80 · 5) = 400
2718, 20, 6, 21, 6, 26, 25decmul1 11843 . . 3 (800 · 5) = 4000
2817, 27eqtr4i 2842 . 2 (𝑁 − 1) = (800 · 5)
29 1nn0 11595 . . . . . . 7 1 ∈ ℕ0
308, 29deccl 11794 . . . . . 6 4001 ∈ ℕ0
3112, 30eqeltri 2892 . . . . 5 𝑁 ∈ ℕ0
3231nn0cni 11591 . . . 4 𝑁 ∈ ℂ
33 npcan 10585 . . . 4 ((𝑁 ∈ ℂ ∧ 1 ∈ ℂ) → ((𝑁 − 1) + 1) = 𝑁)
3432, 11, 33mp2an 675 . . 3 ((𝑁 − 1) + 1) = 𝑁
3534eqcomi 2826 . 2 𝑁 = ((𝑁 − 1) + 1)
36 3nn0 11597 . . 3 3 ∈ ℕ0
37 2nn 11386 . . 3 2 ∈ ℕ
3836, 37decnncl 11799 . 2 32 ∈ ℕ
39 3nn 11392 . 2 3 ∈ ℕ
40 2nn0 11596 . . . . 5 2 ∈ ℕ0
4136, 40deccl 11794 . . . 4 32 ∈ ℕ0
4229, 40deccl 11794 . . . 4 12 ∈ ℕ0
43 2p1e3 11462 . . . . 5 (2 + 1) = 3
4424sqvali 13186 . . . . . . 7 (5↑2) = (5 · 5)
45 5t5e25 11882 . . . . . . 7 (5 · 5) = 25
4644, 45eqtri 2839 . . . . . 6 (5↑2) = 25
47 2cn 11388 . . . . . . . 8 2 ∈ ℂ
48 5t2e10 11879 . . . . . . . 8 (5 · 2) = 10
4924, 47, 48mulcomli 10344 . . . . . . 7 (2 · 5) = 10
5047addid2i 10519 . . . . . . 7 (0 + 2) = 2
5129, 6, 40, 49, 50decaddi 11839 . . . . . 6 ((2 · 5) + 2) = 12
5218, 40, 18, 46, 18, 40, 51, 45decmul1c 11844 . . . . 5 ((5↑2) · 5) = 125
5318, 40, 43, 52numexpp1 16019 . . . 4 (5↑3) = 125
54 6nn0 11600 . . . . 5 6 ∈ ℕ0
5529, 54deccl 11794 . . . 4 16 ∈ ℕ0
56 eqid 2817 . . . . 5 12 = 12
57 eqid 2817 . . . . 5 16 = 16
58 7nn0 11601 . . . . 5 7 ∈ ℕ0
59 7cn 11411 . . . . . . . 8 7 ∈ ℂ
60 7p1e8 11468 . . . . . . . 8 (7 + 1) = 8
6159, 11, 60addcomli 10523 . . . . . . 7 (1 + 7) = 8
6261, 19eqeltri 2892 . . . . . 6 (1 + 7) ∈ ℕ0
63 eqid 2817 . . . . . 6 32 = 32
64 3t1e3 11484 . . . . . . . 8 (3 · 1) = 3
6564oveq1i 6894 . . . . . . 7 ((3 · 1) + 1) = (3 + 1)
66 3p1e4 11464 . . . . . . 7 (3 + 1) = 4
6765, 66eqtri 2839 . . . . . 6 ((3 · 1) + 1) = 4
68 2t1e2 11482 . . . . . . . 8 (2 · 1) = 2
6968, 61oveq12i 6896 . . . . . . 7 ((2 · 1) + (1 + 7)) = (2 + 8)
70 8cn 11415 . . . . . . . 8 8 ∈ ℂ
71 8p2e10 11859 . . . . . . . 8 (8 + 2) = 10
7270, 47, 71addcomli 10523 . . . . . . 7 (2 + 8) = 10
7369, 72eqtri 2839 . . . . . 6 ((2 · 1) + (1 + 7)) = 10
7436, 40, 62, 63, 29, 6, 29, 67, 73decrmac 11837 . . . . 5 ((32 · 1) + (1 + 7)) = 40
75 3t2e6 11485 . . . . . . . 8 (3 · 2) = 6
7675oveq1i 6894 . . . . . . 7 ((3 · 2) + 1) = (6 + 1)
77 6p1e7 11467 . . . . . . 7 (6 + 1) = 7
7876, 77eqtri 2839 . . . . . 6 ((3 · 2) + 1) = 7
79 2t2e4 11483 . . . . . . . 8 (2 · 2) = 4
8079oveq1i 6894 . . . . . . 7 ((2 · 2) + 6) = (4 + 6)
81 6cn 11407 . . . . . . . 8 6 ∈ ℂ
82 4cn 11399 . . . . . . . 8 4 ∈ ℂ
83 6p4e10 11851 . . . . . . . 8 (6 + 4) = 10
8481, 82, 83addcomli 10523 . . . . . . 7 (4 + 6) = 10
8580, 84eqtri 2839 . . . . . 6 ((2 · 2) + 6) = 10
8636, 40, 54, 63, 40, 6, 29, 78, 85decrmac 11837 . . . . 5 ((32 · 2) + 6) = 70
8729, 40, 29, 54, 56, 57, 41, 6, 58, 74, 86decma2c 11832 . . . 4 ((32 · 12) + 16) = 400
88 5p1e6 11466 . . . . . 6 (5 + 1) = 6
89 3cn 11394 . . . . . . 7 3 ∈ ℂ
90 5t3e15 11880 . . . . . . 7 (5 · 3) = 15
9124, 89, 90mulcomli 10344 . . . . . 6 (3 · 5) = 15
9229, 18, 88, 91decsuc 11810 . . . . 5 ((3 · 5) + 1) = 16
9318, 36, 40, 63, 6, 29, 92, 49decmul1c 11844 . . . 4 (32 · 5) = 160
9441, 42, 18, 53, 6, 55, 87, 93decmul2c 11845 . . 3 (32 · (5↑3)) = 4000
9517, 94eqtr4i 2842 . 2 (𝑁 − 1) = (32 · (5↑3))
96 2lt10 11917 . . . 4 2 < 10
97 1nn 11328 . . . . 5 1 ∈ ℕ
98 3lt10 11916 . . . . 5 3 < 10
9997, 40, 36, 98declti 11817 . . . 4 3 < 12
10036, 42, 40, 18, 96, 99decltc 11808 . . 3 32 < 125
101100, 53breqtrri 4882 . 2 32 < (5↑3)
102124001lem3 16081 . 2 ((2↑(𝑁 − 1)) mod 𝑁) = (1 mod 𝑁)
103124001lem4 16082 . 2 (((2↑800) − 1) gcd 𝑁) = 1
1041, 4, 28, 35, 38, 39, 37, 95, 101, 102, 103pockthi 15848 1 𝑁 ∈ ℙ
Colors of variables: wff setvar class
Syntax hints:   = wceq 1637  wcel 2157  (class class class)co 6884  cc 10229  0cc0 10231  1c1 10232   + caddc 10234   · cmul 10236   < clt 10369  cmin 10561  2c2 11368  3c3 11369  4c4 11370  5c5 11371  6c6 11372  7c7 11373  8c8 11374  0cn0 11579  cdc 11779  cexp 13103  cprime 15623
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-rep 4977  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-int 4681  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-1st 7408  df-2nd 7409  df-wrecs 7652  df-recs 7714  df-rdg 7752  df-1o 7806  df-2o 7807  df-oadd 7810  df-er 7989  df-map 8104  df-en 8203  df-dom 8204  df-sdom 8205  df-fin 8206  df-sup 8597  df-inf 8598  df-card 9058  df-cda 9285  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-xnn0 11650  df-z 11664  df-dec 11780  df-uz 11925  df-q 12028  df-rp 12067  df-fz 12570  df-fzo 12710  df-fl 12837  df-mod 12913  df-seq 13045  df-exp 13104  df-hash 13358  df-cj 14082  df-re 14083  df-im 14084  df-sqrt 14218  df-abs 14219  df-dvds 15224  df-gcd 15456  df-prm 15624  df-odz 15707  df-phi 15708  df-pc 15779
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator