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

Theorem 2503prm 16930
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 16914 . 2 139 ∈ ℙ
2 1nn0 12342 . . 3 1 ∈ ℕ0
3 8nn 12161 . . 3 8 ∈ ℕ
42, 3decnncl 12550 . 2 18 ∈ ℕ
5 2503prm.1 . . . . 5 𝑁 = 2503
6 2nn0 12343 . . . . . . . 8 2 ∈ ℕ0
7 5nn0 12346 . . . . . . . 8 5 ∈ ℕ0
86, 7deccl 12545 . . . . . . 7 25 ∈ ℕ0
9 0nn0 12341 . . . . . . 7 0 ∈ ℕ0
108, 9deccl 12545 . . . . . 6 250 ∈ ℕ0
11 2p1e3 12208 . . . . . 6 (2 + 1) = 3
12 eqid 2736 . . . . . 6 2502 = 2502
1310, 6, 11, 12decsuc 12561 . . . . 5 (2502 + 1) = 2503
145, 13eqtr4i 2767 . . . 4 𝑁 = (2502 + 1)
1514oveq1i 7339 . . 3 (𝑁 − 1) = ((2502 + 1) − 1)
16 8nn0 12349 . . . . . 6 8 ∈ ℕ0
172, 16deccl 12545 . . . . 5 18 ∈ ℕ0
18 3nn0 12344 . . . . . 6 3 ∈ ℕ0
192, 18deccl 12545 . . . . 5 13 ∈ ℕ0
20 9nn0 12350 . . . . 5 9 ∈ ℕ0
21 eqid 2736 . . . . 5 139 = 139
22 6nn0 12347 . . . . . 6 6 ∈ ℕ0
232, 22deccl 12545 . . . . 5 16 ∈ ℕ0
24 eqid 2736 . . . . . 6 13 = 13
25 eqid 2736 . . . . . 6 16 = 16
26 7nn0 12348 . . . . . . 7 7 ∈ ℕ0
27 eqid 2736 . . . . . . 7 18 = 18
28 6cn 12157 . . . . . . . . 9 6 ∈ ℂ
29 ax-1cn 11022 . . . . . . . . 9 1 ∈ ℂ
30 6p1e7 12214 . . . . . . . . 9 (6 + 1) = 7
3128, 29, 30addcomli 11260 . . . . . . . 8 (1 + 6) = 7
3226dec0h 12552 . . . . . . . 8 7 = 07
3331, 32eqtri 2764 . . . . . . 7 (1 + 6) = 07
3429mulid1i 11072 . . . . . . . . 9 (1 · 1) = 1
3529addid2i 11256 . . . . . . . . 9 (0 + 1) = 1
3634, 35oveq12i 7341 . . . . . . . 8 ((1 · 1) + (0 + 1)) = (1 + 1)
37 1p1e2 12191 . . . . . . . 8 (1 + 1) = 2
3836, 37eqtri 2764 . . . . . . 7 ((1 · 1) + (0 + 1)) = 2
39 8cn 12163 . . . . . . . . . 10 8 ∈ ℂ
4039mulid1i 11072 . . . . . . . . 9 (8 · 1) = 8
4140oveq1i 7339 . . . . . . . 8 ((8 · 1) + 7) = (8 + 7)
42 8p7e15 12615 . . . . . . . 8 (8 + 7) = 15
4341, 42eqtri 2764 . . . . . . 7 ((8 · 1) + 7) = 15
442, 16, 9, 26, 27, 33, 2, 7, 2, 38, 43decmac 12582 . . . . . 6 ((18 · 1) + (1 + 6)) = 25
4522dec0h 12552 . . . . . . 7 6 = 06
46 3cn 12147 . . . . . . . . . 10 3 ∈ ℂ
4746mulid2i 11073 . . . . . . . . 9 (1 · 3) = 3
4846addid2i 11256 . . . . . . . . 9 (0 + 3) = 3
4947, 48oveq12i 7341 . . . . . . . 8 ((1 · 3) + (0 + 3)) = (3 + 3)
50 3p3e6 12218 . . . . . . . 8 (3 + 3) = 6
5149, 50eqtri 2764 . . . . . . 7 ((1 · 3) + (0 + 3)) = 6
52 4nn0 12345 . . . . . . . 8 4 ∈ ℕ0
53 8t3e24 12646 . . . . . . . 8 (8 · 3) = 24
54 4cn 12151 . . . . . . . . 9 4 ∈ ℂ
55 6p4e10 12602 . . . . . . . . 9 (6 + 4) = 10
5628, 54, 55addcomli 11260 . . . . . . . 8 (4 + 6) = 10
576, 52, 22, 53, 11, 56decaddci2 12592 . . . . . . 7 ((8 · 3) + 6) = 30
582, 16, 9, 22, 27, 45, 18, 9, 18, 51, 57decmac 12582 . . . . . 6 ((18 · 3) + 6) = 60
592, 18, 2, 22, 24, 25, 17, 9, 22, 44, 58decma2c 12583 . . . . 5 ((18 · 13) + 16) = 250
60 9cn 12166 . . . . . . . . 9 9 ∈ ℂ
6160mulid2i 11073 . . . . . . . 8 (1 · 9) = 9
6261oveq1i 7339 . . . . . . 7 ((1 · 9) + 7) = (9 + 7)
63 9p7e16 12622 . . . . . . 7 (9 + 7) = 16
6462, 63eqtri 2764 . . . . . 6 ((1 · 9) + 7) = 16
65 9t8e72 12658 . . . . . . 7 (9 · 8) = 72
6660, 39, 65mulcomli 11077 . . . . . 6 (8 · 9) = 72
6720, 2, 16, 27, 6, 26, 64, 66decmul1c 12595 . . . . 5 (18 · 9) = 162
6817, 19, 20, 21, 6, 23, 59, 67decmul2c 12596 . . . 4 (18 · 139) = 2502
6910, 6deccl 12545 . . . . . 6 2502 ∈ ℕ0
7069nn0cni 12338 . . . . 5 2502 ∈ ℂ
7170, 29pncan3oi 11330 . . . 4 ((2502 + 1) − 1) = 2502
7268, 71eqtr4i 2767 . . 3 (18 · 139) = ((2502 + 1) − 1)
7315, 72eqtr4i 2767 . 2 (𝑁 − 1) = (18 · 139)
7410, 18deccl 12545 . . . . . 6 2503 ∈ ℕ0
755, 74eqeltri 2833 . . . . 5 𝑁 ∈ ℕ0
7675nn0cni 12338 . . . 4 𝑁 ∈ ℂ
77 npcan 11323 . . . 4 ((𝑁 ∈ ℂ ∧ 1 ∈ ℂ) → ((𝑁 − 1) + 1) = 𝑁)
7876, 29, 77mp2an 689 . . 3 ((𝑁 − 1) + 1) = 𝑁
7978eqcomi 2745 . 2 𝑁 = ((𝑁 − 1) + 1)
80 1nn 12077 . 2 1 ∈ ℕ
81 2nn 12139 . 2 2 ∈ ℕ
8219, 20deccl 12545 . . . . 5 139 ∈ ℕ0
8382numexp1 16867 . . . 4 (139↑1) = 139
8483oveq2i 7340 . . 3 (18 · (139↑1)) = (18 · 139)
8573, 84eqtr4i 2767 . 2 (𝑁 − 1) = (18 · (139↑1))
86 8lt10 12662 . . . 4 8 < 10
87 1lt10 12669 . . . . 5 1 < 10
8880, 18, 2, 87declti 12568 . . . 4 1 < 13
892, 19, 16, 20, 86, 88decltc 12559 . . 3 18 < 139
9089, 83breqtrri 5116 . 2 18 < (139↑1)
9152503lem2 16928 . 2 ((2↑(𝑁 − 1)) mod 𝑁) = (1 mod 𝑁)
9252503lem3 16929 . 2 (((2↑18) − 1) gcd 𝑁) = 1
931, 4, 73, 79, 4, 80, 81, 85, 90, 91, 92pockthi 16697 1 𝑁 ∈ ℙ
Colors of variables: wff setvar class
Syntax hints:   = wceq 1540  wcel 2105  (class class class)co 7329  cc 10962  0cc0 10964  1c1 10965   + caddc 10967   · cmul 10969   < clt 11102  cmin 11298  2c2 12121  3c3 12122  4c4 12123  5c5 12124  6c6 12125  7c7 12126  8c8 12127  9c9 12128  0cn0 12326  cdc 12530  cexp 13875  cprime 16465
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1796  ax-4 1810  ax-5 1912  ax-6 1970  ax-7 2010  ax-8 2107  ax-9 2115  ax-10 2136  ax-11 2153  ax-12 2170  ax-ext 2707  ax-rep 5226  ax-sep 5240  ax-nul 5247  ax-pow 5305  ax-pr 5369  ax-un 7642  ax-cnex 11020  ax-resscn 11021  ax-1cn 11022  ax-icn 11023  ax-addcl 11024  ax-addrcl 11025  ax-mulcl 11026  ax-mulrcl 11027  ax-mulcom 11028  ax-addass 11029  ax-mulass 11030  ax-distr 11031  ax-i2m1 11032  ax-1ne0 11033  ax-1rid 11034  ax-rnegex 11035  ax-rrecex 11036  ax-cnre 11037  ax-pre-lttri 11038  ax-pre-lttrn 11039  ax-pre-ltadd 11040  ax-pre-mulgt0 11041  ax-pre-sup 11042
This theorem depends on definitions:  df-bi 206  df-an 397  df-or 845  df-3or 1087  df-3an 1088  df-tru 1543  df-fal 1553  df-ex 1781  df-nf 1785  df-sb 2067  df-mo 2538  df-eu 2567  df-clab 2714  df-cleq 2728  df-clel 2814  df-nfc 2886  df-ne 2941  df-nel 3047  df-ral 3062  df-rex 3071  df-rmo 3349  df-reu 3350  df-rab 3404  df-v 3443  df-sbc 3727  df-csb 3843  df-dif 3900  df-un 3902  df-in 3904  df-ss 3914  df-pss 3916  df-nul 4269  df-if 4473  df-pw 4548  df-sn 4573  df-pr 4575  df-op 4579  df-uni 4852  df-int 4894  df-iun 4940  df-br 5090  df-opab 5152  df-mpt 5173  df-tr 5207  df-id 5512  df-eprel 5518  df-po 5526  df-so 5527  df-fr 5569  df-we 5571  df-xp 5620  df-rel 5621  df-cnv 5622  df-co 5623  df-dm 5624  df-rn 5625  df-res 5626  df-ima 5627  df-pred 6232  df-ord 6299  df-on 6300  df-lim 6301  df-suc 6302  df-iota 6425  df-fun 6475  df-fn 6476  df-f 6477  df-f1 6478  df-fo 6479  df-f1o 6480  df-fv 6481  df-riota 7286  df-ov 7332  df-oprab 7333  df-mpo 7334  df-om 7773  df-1st 7891  df-2nd 7892  df-frecs 8159  df-wrecs 8190  df-recs 8264  df-rdg 8303  df-1o 8359  df-2o 8360  df-oadd 8363  df-er 8561  df-en 8797  df-dom 8798  df-sdom 8799  df-fin 8800  df-sup 9291  df-inf 9292  df-dju 9750  df-card 9788  df-pnf 11104  df-mnf 11105  df-xr 11106  df-ltxr 11107  df-le 11108  df-sub 11300  df-neg 11301  df-div 11726  df-nn 12067  df-2 12129  df-3 12130  df-4 12131  df-5 12132  df-6 12133  df-7 12134  df-8 12135  df-9 12136  df-n0 12327  df-xnn0 12399  df-z 12413  df-dec 12531  df-uz 12676  df-q 12782  df-rp 12824  df-fz 13333  df-fzo 13476  df-fl 13605  df-mod 13683  df-seq 13815  df-exp 13876  df-hash 14138  df-cj 14901  df-re 14902  df-im 14903  df-sqrt 15037  df-abs 15038  df-dvds 16055  df-gcd 16293  df-prm 16466  df-odz 16555  df-phi 16556  df-pc 16627
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator