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

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

Proof of Theorem 2503prm
StepHypRef Expression
1 139prm 16303 . 2 139 ∈ ℙ
2 1nn0 11718 . . 3 1 ∈ ℕ0
3 8nn 11533 . . 3 8 ∈ ℕ
42, 3decnncl 11925 . 2 18 ∈ ℕ
5 2503prm.1 . . . . 5 𝑁 = 2503
6 2nn0 11719 . . . . . . . 8 2 ∈ ℕ0
7 5nn0 11722 . . . . . . . 8 5 ∈ ℕ0
86, 7deccl 11919 . . . . . . 7 25 ∈ ℕ0
9 0nn0 11717 . . . . . . 7 0 ∈ ℕ0
108, 9deccl 11919 . . . . . 6 250 ∈ ℕ0
11 2p1e3 11582 . . . . . 6 (2 + 1) = 3
12 eqid 2772 . . . . . 6 2502 = 2502
1310, 6, 11, 12decsuc 11936 . . . . 5 (2502 + 1) = 2503
145, 13eqtr4i 2799 . . . 4 𝑁 = (2502 + 1)
1514oveq1i 6980 . . 3 (𝑁 − 1) = ((2502 + 1) − 1)
16 8nn0 11725 . . . . . 6 8 ∈ ℕ0
172, 16deccl 11919 . . . . 5 18 ∈ ℕ0
18 3nn0 11720 . . . . . 6 3 ∈ ℕ0
192, 18deccl 11919 . . . . 5 13 ∈ ℕ0
20 9nn0 11726 . . . . 5 9 ∈ ℕ0
21 eqid 2772 . . . . 5 139 = 139
22 6nn0 11723 . . . . . 6 6 ∈ ℕ0
232, 22deccl 11919 . . . . 5 16 ∈ ℕ0
24 eqid 2772 . . . . . 6 13 = 13
25 eqid 2772 . . . . . 6 16 = 16
26 7nn0 11724 . . . . . . 7 7 ∈ ℕ0
27 eqid 2772 . . . . . . 7 18 = 18
28 6cn 11527 . . . . . . . . 9 6 ∈ ℂ
29 ax-1cn 10385 . . . . . . . . 9 1 ∈ ℂ
30 6p1e7 11588 . . . . . . . . 9 (6 + 1) = 7
3128, 29, 30addcomli 10624 . . . . . . . 8 (1 + 6) = 7
3226dec0h 11927 . . . . . . . 8 7 = 07
3331, 32eqtri 2796 . . . . . . 7 (1 + 6) = 07
3429mulid1i 10436 . . . . . . . . 9 (1 · 1) = 1
3529addid2i 10620 . . . . . . . . 9 (0 + 1) = 1
3634, 35oveq12i 6982 . . . . . . . 8 ((1 · 1) + (0 + 1)) = (1 + 1)
37 1p1e2 11565 . . . . . . . 8 (1 + 1) = 2
3836, 37eqtri 2796 . . . . . . 7 ((1 · 1) + (0 + 1)) = 2
39 8cn 11535 . . . . . . . . . 10 8 ∈ ℂ
4039mulid1i 10436 . . . . . . . . 9 (8 · 1) = 8
4140oveq1i 6980 . . . . . . . 8 ((8 · 1) + 7) = (8 + 7)
42 8p7e15 11991 . . . . . . . 8 (8 + 7) = 15
4341, 42eqtri 2796 . . . . . . 7 ((8 · 1) + 7) = 15
442, 16, 9, 26, 27, 33, 2, 7, 2, 38, 43decmac 11957 . . . . . 6 ((18 · 1) + (1 + 6)) = 25
4522dec0h 11927 . . . . . . 7 6 = 06
46 3cn 11514 . . . . . . . . . 10 3 ∈ ℂ
4746mulid2i 10437 . . . . . . . . 9 (1 · 3) = 3
4846addid2i 10620 . . . . . . . . 9 (0 + 3) = 3
4947, 48oveq12i 6982 . . . . . . . 8 ((1 · 3) + (0 + 3)) = (3 + 3)
50 3p3e6 11592 . . . . . . . 8 (3 + 3) = 6
5149, 50eqtri 2796 . . . . . . 7 ((1 · 3) + (0 + 3)) = 6
52 4nn0 11721 . . . . . . . 8 4 ∈ ℕ0
53 8t3e24 12022 . . . . . . . 8 (8 · 3) = 24
54 4cn 11519 . . . . . . . . 9 4 ∈ ℂ
55 6p4e10 11978 . . . . . . . . 9 (6 + 4) = 10
5628, 54, 55addcomli 10624 . . . . . . . 8 (4 + 6) = 10
576, 52, 22, 53, 11, 56decaddci2 11967 . . . . . . 7 ((8 · 3) + 6) = 30
582, 16, 9, 22, 27, 45, 18, 9, 18, 51, 57decmac 11957 . . . . . 6 ((18 · 3) + 6) = 60
592, 18, 2, 22, 24, 25, 17, 9, 22, 44, 58decma2c 11958 . . . . 5 ((18 · 13) + 16) = 250
60 9cn 11539 . . . . . . . . 9 9 ∈ ℂ
6160mulid2i 10437 . . . . . . . 8 (1 · 9) = 9
6261oveq1i 6980 . . . . . . 7 ((1 · 9) + 7) = (9 + 7)
63 9p7e16 11998 . . . . . . 7 (9 + 7) = 16
6462, 63eqtri 2796 . . . . . 6 ((1 · 9) + 7) = 16
65 9t8e72 12034 . . . . . . 7 (9 · 8) = 72
6660, 39, 65mulcomli 10441 . . . . . 6 (8 · 9) = 72
6720, 2, 16, 27, 6, 26, 64, 66decmul1c 11971 . . . . 5 (18 · 9) = 162
6817, 19, 20, 21, 6, 23, 59, 67decmul2c 11972 . . . 4 (18 · 139) = 2502
6910, 6deccl 11919 . . . . . 6 2502 ∈ ℕ0
7069nn0cni 11713 . . . . 5 2502 ∈ ℂ
7170, 29pncan3oi 10695 . . . 4 ((2502 + 1) − 1) = 2502
7268, 71eqtr4i 2799 . . 3 (18 · 139) = ((2502 + 1) − 1)
7315, 72eqtr4i 2799 . 2 (𝑁 − 1) = (18 · 139)
7410, 18deccl 11919 . . . . . 6 2503 ∈ ℕ0
755, 74eqeltri 2856 . . . . 5 𝑁 ∈ ℕ0
7675nn0cni 11713 . . . 4 𝑁 ∈ ℂ
77 npcan 10688 . . . 4 ((𝑁 ∈ ℂ ∧ 1 ∈ ℂ) → ((𝑁 − 1) + 1) = 𝑁)
7876, 29, 77mp2an 679 . . 3 ((𝑁 − 1) + 1) = 𝑁
7978eqcomi 2781 . 2 𝑁 = ((𝑁 − 1) + 1)
80 1nn 11444 . 2 1 ∈ ℕ
81 2nn 11506 . 2 2 ∈ ℕ
8219, 20deccl 11919 . . . . 5 139 ∈ ℕ0
8382numexp1 16259 . . . 4 (139↑1) = 139
8483oveq2i 6981 . . 3 (18 · (139↑1)) = (18 · 139)
8573, 84eqtr4i 2799 . 2 (𝑁 − 1) = (18 · (139↑1))
86 8lt10 12038 . . . 4 8 < 10
87 1lt10 12045 . . . . 5 1 < 10
8880, 18, 2, 87declti 11943 . . . 4 1 < 13
892, 19, 16, 20, 86, 88decltc 11934 . . 3 18 < 139
9089, 83breqtrri 4950 . 2 18 < (139↑1)
9152503lem2 16317 . 2 ((2↑(𝑁 − 1)) mod 𝑁) = (1 mod 𝑁)
9252503lem3 16318 . 2 (((2↑18) − 1) gcd 𝑁) = 1
931, 4, 73, 79, 4, 80, 81, 85, 90, 91, 92pockthi 16089 1 𝑁 ∈ ℙ
Colors of variables: wff setvar class
Syntax hints:   = wceq 1507  wcel 2048  (class class class)co 6970  cc 10325  0cc0 10327  1c1 10328   + caddc 10330   · cmul 10332   < clt 10466  cmin 10662  2c2 11488  3c3 11489  4c4 11490  5c5 11491  6c6 11492  7c7 11493  8c8 11494  9c9 11495  0cn0 11700  cdc 11904  cexp 13237  cprime 15861
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1758  ax-4 1772  ax-5 1869  ax-6 1928  ax-7 1964  ax-8 2050  ax-9 2057  ax-10 2077  ax-11 2091  ax-12 2104  ax-13 2299  ax-ext 2745  ax-rep 5043  ax-sep 5054  ax-nul 5061  ax-pow 5113  ax-pr 5180  ax-un 7273  ax-cnex 10383  ax-resscn 10384  ax-1cn 10385  ax-icn 10386  ax-addcl 10387  ax-addrcl 10388  ax-mulcl 10389  ax-mulrcl 10390  ax-mulcom 10391  ax-addass 10392  ax-mulass 10393  ax-distr 10394  ax-i2m1 10395  ax-1ne0 10396  ax-1rid 10397  ax-rnegex 10398  ax-rrecex 10399  ax-cnre 10400  ax-pre-lttri 10401  ax-pre-lttrn 10402  ax-pre-ltadd 10403  ax-pre-mulgt0 10404  ax-pre-sup 10405
This theorem depends on definitions:  df-bi 199  df-an 388  df-or 834  df-3or 1069  df-3an 1070  df-tru 1510  df-ex 1743  df-nf 1747  df-sb 2014  df-mo 2544  df-eu 2580  df-clab 2754  df-cleq 2765  df-clel 2840  df-nfc 2912  df-ne 2962  df-nel 3068  df-ral 3087  df-rex 3088  df-reu 3089  df-rmo 3090  df-rab 3091  df-v 3411  df-sbc 3678  df-csb 3783  df-dif 3828  df-un 3830  df-in 3832  df-ss 3839  df-pss 3841  df-nul 4174  df-if 4345  df-pw 4418  df-sn 4436  df-pr 4438  df-tp 4440  df-op 4442  df-uni 4707  df-int 4744  df-iun 4788  df-br 4924  df-opab 4986  df-mpt 5003  df-tr 5025  df-id 5305  df-eprel 5310  df-po 5319  df-so 5320  df-fr 5359  df-we 5361  df-xp 5406  df-rel 5407  df-cnv 5408  df-co 5409  df-dm 5410  df-rn 5411  df-res 5412  df-ima 5413  df-pred 5980  df-ord 6026  df-on 6027  df-lim 6028  df-suc 6029  df-iota 6146  df-fun 6184  df-fn 6185  df-f 6186  df-f1 6187  df-fo 6188  df-f1o 6189  df-fv 6190  df-riota 6931  df-ov 6973  df-oprab 6974  df-mpo 6975  df-om 7391  df-1st 7494  df-2nd 7495  df-wrecs 7743  df-recs 7805  df-rdg 7843  df-1o 7897  df-2o 7898  df-oadd 7901  df-er 8081  df-map 8200  df-en 8299  df-dom 8300  df-sdom 8301  df-fin 8302  df-sup 8693  df-inf 8694  df-dju 9116  df-card 9154  df-pnf 10468  df-mnf 10469  df-xr 10470  df-ltxr 10471  df-le 10472  df-sub 10664  df-neg 10665  df-div 11091  df-nn 11432  df-2 11496  df-3 11497  df-4 11498  df-5 11499  df-6 11500  df-7 11501  df-8 11502  df-9 11503  df-n0 11701  df-xnn0 11773  df-z 11787  df-dec 11905  df-uz 12052  df-q 12156  df-rp 12198  df-fz 12702  df-fzo 12843  df-fl 12970  df-mod 13046  df-seq 13178  df-exp 13238  df-hash 13499  df-cj 14309  df-re 14310  df-im 14311  df-sqrt 14445  df-abs 14446  df-dvds 15458  df-gcd 15694  df-prm 15862  df-odz 15948  df-phi 15949  df-pc 16020
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator