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

Theorem 4001prm 17121
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 17085 . 2 5 ∈ ℙ
2 8nn 12345 . . . 4 8 ∈ ℕ
32decnncl2 12739 . . 3 80 ∈ ℕ
43decnncl2 12739 . 2 800 ∈ ℕ
5 4nn0 12529 . . . . . . . 8 4 ∈ ℕ0
6 0nn0 12525 . . . . . . . 8 0 ∈ ℕ0
75, 6deccl 12730 . . . . . . 7 40 ∈ ℕ0
87, 6deccl 12730 . . . . . 6 400 ∈ ℕ0
98, 6deccl 12730 . . . . 5 4000 ∈ ℕ0
109nn0cni 12522 . . . 4 4000 ∈ ℂ
11 ax-1cn 11204 . . . 4 1 ∈ ℂ
12 4001prm.1 . . . . 5 𝑁 = 4001
1311addlidi 11440 . . . . . 6 (0 + 1) = 1
14 eqid 2728 . . . . . 6 4000 = 4000
158, 6, 13, 14decsuc 12746 . . . . 5 (4000 + 1) = 4001
1612, 15eqtr4i 2759 . . . 4 𝑁 = (4000 + 1)
1710, 11, 16mvrraddi 11515 . . 3 (𝑁 − 1) = 4000
18 5nn0 12530 . . . 4 5 ∈ ℕ0
19 8nn0 12533 . . . . 5 8 ∈ ℕ0
2019, 6deccl 12730 . . . 4 80 ∈ ℕ0
21 eqid 2728 . . . 4 800 = 800
22 eqid 2728 . . . . 5 80 = 80
23 8t5e40 12833 . . . . 5 (8 · 5) = 40
24 5cn 12338 . . . . . 6 5 ∈ ℂ
2524mul02i 11441 . . . . 5 (0 · 5) = 0
2618, 19, 6, 22, 23, 25decmul1 12779 . . . 4 (80 · 5) = 400
2718, 20, 6, 21, 26, 25decmul1 12779 . . 3 (800 · 5) = 4000
2817, 27eqtr4i 2759 . 2 (𝑁 − 1) = (800 · 5)
29 1nn0 12526 . . . . . . 7 1 ∈ ℕ0
308, 29deccl 12730 . . . . . 6 4001 ∈ ℕ0
3112, 30eqeltri 2825 . . . . 5 𝑁 ∈ ℕ0
3231nn0cni 12522 . . . 4 𝑁 ∈ ℂ
33 npcan 11507 . . . 4 ((𝑁 ∈ ℂ ∧ 1 ∈ ℂ) → ((𝑁 − 1) + 1) = 𝑁)
3432, 11, 33mp2an 690 . . 3 ((𝑁 − 1) + 1) = 𝑁
3534eqcomi 2737 . 2 𝑁 = ((𝑁 − 1) + 1)
36 3nn0 12528 . . 3 3 ∈ ℕ0
37 2nn 12323 . . 3 2 ∈ ℕ
3836, 37decnncl 12735 . 2 32 ∈ ℕ
39 3nn 12329 . 2 3 ∈ ℕ
40 2nn0 12527 . . . . 5 2 ∈ ℕ0
4136, 40deccl 12730 . . . 4 32 ∈ ℕ0
4229, 40deccl 12730 . . . 4 12 ∈ ℕ0
43 2p1e3 12392 . . . . 5 (2 + 1) = 3
4424sqvali 14183 . . . . . . 7 (5↑2) = (5 · 5)
45 5t5e25 12818 . . . . . . 7 (5 · 5) = 25
4644, 45eqtri 2756 . . . . . 6 (5↑2) = 25
47 2cn 12325 . . . . . . . 8 2 ∈ ℂ
48 5t2e10 12815 . . . . . . . 8 (5 · 2) = 10
4924, 47, 48mulcomli 11261 . . . . . . 7 (2 · 5) = 10
5047addlidi 11440 . . . . . . 7 (0 + 2) = 2
5129, 6, 40, 49, 50decaddi 12775 . . . . . 6 ((2 · 5) + 2) = 12
5218, 40, 18, 46, 18, 40, 51, 45decmul1c 12780 . . . . 5 ((5↑2) · 5) = 125
5318, 40, 43, 52numexpp1 17054 . . . 4 (5↑3) = 125
54 6nn0 12531 . . . . 5 6 ∈ ℕ0
5529, 54deccl 12730 . . . 4 16 ∈ ℕ0
56 eqid 2728 . . . . 5 12 = 12
57 eqid 2728 . . . . 5 16 = 16
58 7nn0 12532 . . . . 5 7 ∈ ℕ0
59 7cn 12344 . . . . . . . 8 7 ∈ ℂ
60 7p1e8 12399 . . . . . . . 8 (7 + 1) = 8
6159, 11, 60addcomli 11444 . . . . . . 7 (1 + 7) = 8
6261, 19eqeltri 2825 . . . . . 6 (1 + 7) ∈ ℕ0
63 eqid 2728 . . . . . 6 32 = 32
64 3t1e3 12415 . . . . . . . 8 (3 · 1) = 3
6564oveq1i 7436 . . . . . . 7 ((3 · 1) + 1) = (3 + 1)
66 3p1e4 12395 . . . . . . 7 (3 + 1) = 4
6765, 66eqtri 2756 . . . . . 6 ((3 · 1) + 1) = 4
68 2t1e2 12413 . . . . . . . 8 (2 · 1) = 2
6968, 61oveq12i 7438 . . . . . . 7 ((2 · 1) + (1 + 7)) = (2 + 8)
70 8cn 12347 . . . . . . . 8 8 ∈ ℂ
71 8p2e10 12795 . . . . . . . 8 (8 + 2) = 10
7270, 47, 71addcomli 11444 . . . . . . 7 (2 + 8) = 10
7369, 72eqtri 2756 . . . . . 6 ((2 · 1) + (1 + 7)) = 10
7436, 40, 62, 63, 29, 6, 29, 67, 73decrmac 12773 . . . . 5 ((32 · 1) + (1 + 7)) = 40
75 3t2e6 12416 . . . . . . . 8 (3 · 2) = 6
7675oveq1i 7436 . . . . . . 7 ((3 · 2) + 1) = (6 + 1)
77 6p1e7 12398 . . . . . . 7 (6 + 1) = 7
7876, 77eqtri 2756 . . . . . 6 ((3 · 2) + 1) = 7
79 2t2e4 12414 . . . . . . . 8 (2 · 2) = 4
8079oveq1i 7436 . . . . . . 7 ((2 · 2) + 6) = (4 + 6)
81 6cn 12341 . . . . . . . 8 6 ∈ ℂ
82 4cn 12335 . . . . . . . 8 4 ∈ ℂ
83 6p4e10 12787 . . . . . . . 8 (6 + 4) = 10
8481, 82, 83addcomli 11444 . . . . . . 7 (4 + 6) = 10
8580, 84eqtri 2756 . . . . . 6 ((2 · 2) + 6) = 10
8636, 40, 54, 63, 40, 6, 29, 78, 85decrmac 12773 . . . . 5 ((32 · 2) + 6) = 70
8729, 40, 29, 54, 56, 57, 41, 6, 58, 74, 86decma2c 12768 . . . 4 ((32 · 12) + 16) = 400
88 5p1e6 12397 . . . . . 6 (5 + 1) = 6
89 3cn 12331 . . . . . . 7 3 ∈ ℂ
90 5t3e15 12816 . . . . . . 7 (5 · 3) = 15
9124, 89, 90mulcomli 11261 . . . . . 6 (3 · 5) = 15
9229, 18, 88, 91decsuc 12746 . . . . 5 ((3 · 5) + 1) = 16
9318, 36, 40, 63, 6, 29, 92, 49decmul1c 12780 . . . 4 (32 · 5) = 160
9441, 42, 18, 53, 6, 55, 87, 93decmul2c 12781 . . 3 (32 · (5↑3)) = 4000
9517, 94eqtr4i 2759 . 2 (𝑁 − 1) = (32 · (5↑3))
96 2lt10 12853 . . . 4 2 < 10
97 1nn 12261 . . . . 5 1 ∈ ℕ
98 3lt10 12852 . . . . 5 3 < 10
9997, 40, 36, 98declti 12753 . . . 4 3 < 12
10036, 42, 40, 18, 96, 99decltc 12744 . . 3 32 < 125
101100, 53breqtrri 5179 . 2 32 < (5↑3)
102124001lem3 17119 . 2 ((2↑(𝑁 − 1)) mod 𝑁) = (1 mod 𝑁)
103124001lem4 17120 . 2 (((2↑800) − 1) gcd 𝑁) = 1
1041, 4, 28, 35, 38, 39, 37, 95, 101, 102, 103pockthi 16883 1 𝑁 ∈ ℙ
Colors of variables: wff setvar class
Syntax hints:   = wceq 1533  wcel 2098  (class class class)co 7426  cc 11144  0cc0 11146  1c1 11147   + caddc 11149   · cmul 11151   < clt 11286  cmin 11482  2c2 12305  3c3 12306  4c4 12307  5c5 12308  6c6 12309  7c7 12310  8c8 12311  0cn0 12510  cdc 12715  cexp 14066  cprime 16649
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1789  ax-4 1803  ax-5 1905  ax-6 1963  ax-7 2003  ax-8 2100  ax-9 2108  ax-10 2129  ax-11 2146  ax-12 2166  ax-ext 2699  ax-rep 5289  ax-sep 5303  ax-nul 5310  ax-pow 5369  ax-pr 5433  ax-un 7746  ax-cnex 11202  ax-resscn 11203  ax-1cn 11204  ax-icn 11205  ax-addcl 11206  ax-addrcl 11207  ax-mulcl 11208  ax-mulrcl 11209  ax-mulcom 11210  ax-addass 11211  ax-mulass 11212  ax-distr 11213  ax-i2m1 11214  ax-1ne0 11215  ax-1rid 11216  ax-rnegex 11217  ax-rrecex 11218  ax-cnre 11219  ax-pre-lttri 11220  ax-pre-lttrn 11221  ax-pre-ltadd 11222  ax-pre-mulgt0 11223  ax-pre-sup 11224
This theorem depends on definitions:  df-bi 206  df-an 395  df-or 846  df-3or 1085  df-3an 1086  df-tru 1536  df-fal 1546  df-ex 1774  df-nf 1778  df-sb 2060  df-mo 2529  df-eu 2558  df-clab 2706  df-cleq 2720  df-clel 2806  df-nfc 2881  df-ne 2938  df-nel 3044  df-ral 3059  df-rex 3068  df-rmo 3374  df-reu 3375  df-rab 3431  df-v 3475  df-sbc 3779  df-csb 3895  df-dif 3952  df-un 3954  df-in 3956  df-ss 3966  df-pss 3968  df-nul 4327  df-if 4533  df-pw 4608  df-sn 4633  df-pr 4635  df-op 4639  df-uni 4913  df-int 4954  df-iun 5002  df-br 5153  df-opab 5215  df-mpt 5236  df-tr 5270  df-id 5580  df-eprel 5586  df-po 5594  df-so 5595  df-fr 5637  df-we 5639  df-xp 5688  df-rel 5689  df-cnv 5690  df-co 5691  df-dm 5692  df-rn 5693  df-res 5694  df-ima 5695  df-pred 6310  df-ord 6377  df-on 6378  df-lim 6379  df-suc 6380  df-iota 6505  df-fun 6555  df-fn 6556  df-f 6557  df-f1 6558  df-fo 6559  df-f1o 6560  df-fv 6561  df-riota 7382  df-ov 7429  df-oprab 7430  df-mpo 7431  df-om 7877  df-1st 7999  df-2nd 8000  df-frecs 8293  df-wrecs 8324  df-recs 8398  df-rdg 8437  df-1o 8493  df-2o 8494  df-oadd 8497  df-er 8731  df-en 8971  df-dom 8972  df-sdom 8973  df-fin 8974  df-sup 9473  df-inf 9474  df-dju 9932  df-card 9970  df-pnf 11288  df-mnf 11289  df-xr 11290  df-ltxr 11291  df-le 11292  df-sub 11484  df-neg 11485  df-div 11910  df-nn 12251  df-2 12313  df-3 12314  df-4 12315  df-5 12316  df-6 12317  df-7 12318  df-8 12319  df-9 12320  df-n0 12511  df-xnn0 12583  df-z 12597  df-dec 12716  df-uz 12861  df-q 12971  df-rp 13015  df-fz 13525  df-fzo 13668  df-fl 13797  df-mod 13875  df-seq 14007  df-exp 14067  df-hash 14330  df-cj 15086  df-re 15087  df-im 15088  df-sqrt 15222  df-abs 15223  df-dvds 16239  df-gcd 16477  df-prm 16650  df-odz 16741  df-phi 16742  df-pc 16813
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator