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

Theorem 2503prm 17137
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 17121 . 2 139 ∈ ℙ
2 1nn0 12534 . . 3 1 ∈ ℕ0
3 8nn 12353 . . 3 8 ∈ ℕ
42, 3decnncl 12743 . 2 18 ∈ ℕ
5 2503prm.1 . . . . 5 𝑁 = 2503
6 2nn0 12535 . . . . . . . 8 2 ∈ ℕ0
7 5nn0 12538 . . . . . . . 8 5 ∈ ℕ0
86, 7deccl 12738 . . . . . . 7 25 ∈ ℕ0
9 0nn0 12533 . . . . . . 7 0 ∈ ℕ0
108, 9deccl 12738 . . . . . 6 250 ∈ ℕ0
11 2p1e3 12400 . . . . . 6 (2 + 1) = 3
12 eqid 2726 . . . . . 6 2502 = 2502
1310, 6, 11, 12decsuc 12754 . . . . 5 (2502 + 1) = 2503
145, 13eqtr4i 2757 . . . 4 𝑁 = (2502 + 1)
1514oveq1i 7426 . . 3 (𝑁 − 1) = ((2502 + 1) − 1)
16 8nn0 12541 . . . . . 6 8 ∈ ℕ0
172, 16deccl 12738 . . . . 5 18 ∈ ℕ0
18 3nn0 12536 . . . . . 6 3 ∈ ℕ0
192, 18deccl 12738 . . . . 5 13 ∈ ℕ0
20 9nn0 12542 . . . . 5 9 ∈ ℕ0
21 eqid 2726 . . . . 5 139 = 139
22 6nn0 12539 . . . . . 6 6 ∈ ℕ0
232, 22deccl 12738 . . . . 5 16 ∈ ℕ0
24 eqid 2726 . . . . . 6 13 = 13
25 eqid 2726 . . . . . 6 16 = 16
26 7nn0 12540 . . . . . . 7 7 ∈ ℕ0
27 eqid 2726 . . . . . . 7 18 = 18
28 6cn 12349 . . . . . . . . 9 6 ∈ ℂ
29 ax-1cn 11207 . . . . . . . . 9 1 ∈ ℂ
30 6p1e7 12406 . . . . . . . . 9 (6 + 1) = 7
3128, 29, 30addcomli 11447 . . . . . . . 8 (1 + 6) = 7
3226dec0h 12745 . . . . . . . 8 7 = 07
3331, 32eqtri 2754 . . . . . . 7 (1 + 6) = 07
3429mulridi 11259 . . . . . . . . 9 (1 · 1) = 1
3529addlidi 11443 . . . . . . . . 9 (0 + 1) = 1
3634, 35oveq12i 7428 . . . . . . . 8 ((1 · 1) + (0 + 1)) = (1 + 1)
37 1p1e2 12383 . . . . . . . 8 (1 + 1) = 2
3836, 37eqtri 2754 . . . . . . 7 ((1 · 1) + (0 + 1)) = 2
39 8cn 12355 . . . . . . . . . 10 8 ∈ ℂ
4039mulridi 11259 . . . . . . . . 9 (8 · 1) = 8
4140oveq1i 7426 . . . . . . . 8 ((8 · 1) + 7) = (8 + 7)
42 8p7e15 12808 . . . . . . . 8 (8 + 7) = 15
4341, 42eqtri 2754 . . . . . . 7 ((8 · 1) + 7) = 15
442, 16, 9, 26, 27, 33, 2, 7, 2, 38, 43decmac 12775 . . . . . 6 ((18 · 1) + (1 + 6)) = 25
4522dec0h 12745 . . . . . . 7 6 = 06
46 3cn 12339 . . . . . . . . . 10 3 ∈ ℂ
4746mullidi 11260 . . . . . . . . 9 (1 · 3) = 3
4846addlidi 11443 . . . . . . . . 9 (0 + 3) = 3
4947, 48oveq12i 7428 . . . . . . . 8 ((1 · 3) + (0 + 3)) = (3 + 3)
50 3p3e6 12410 . . . . . . . 8 (3 + 3) = 6
5149, 50eqtri 2754 . . . . . . 7 ((1 · 3) + (0 + 3)) = 6
52 4nn0 12537 . . . . . . . 8 4 ∈ ℕ0
53 8t3e24 12839 . . . . . . . 8 (8 · 3) = 24
54 4cn 12343 . . . . . . . . 9 4 ∈ ℂ
55 6p4e10 12795 . . . . . . . . 9 (6 + 4) = 10
5628, 54, 55addcomli 11447 . . . . . . . 8 (4 + 6) = 10
576, 52, 22, 53, 11, 56decaddci2 12785 . . . . . . 7 ((8 · 3) + 6) = 30
582, 16, 9, 22, 27, 45, 18, 9, 18, 51, 57decmac 12775 . . . . . 6 ((18 · 3) + 6) = 60
592, 18, 2, 22, 24, 25, 17, 9, 22, 44, 58decma2c 12776 . . . . 5 ((18 · 13) + 16) = 250
60 9cn 12358 . . . . . . . . 9 9 ∈ ℂ
6160mullidi 11260 . . . . . . . 8 (1 · 9) = 9
6261oveq1i 7426 . . . . . . 7 ((1 · 9) + 7) = (9 + 7)
63 9p7e16 12815 . . . . . . 7 (9 + 7) = 16
6462, 63eqtri 2754 . . . . . 6 ((1 · 9) + 7) = 16
65 9t8e72 12851 . . . . . . 7 (9 · 8) = 72
6660, 39, 65mulcomli 11264 . . . . . 6 (8 · 9) = 72
6720, 2, 16, 27, 6, 26, 64, 66decmul1c 12788 . . . . 5 (18 · 9) = 162
6817, 19, 20, 21, 6, 23, 59, 67decmul2c 12789 . . . 4 (18 · 139) = 2502
6910, 6deccl 12738 . . . . . 6 2502 ∈ ℕ0
7069nn0cni 12530 . . . . 5 2502 ∈ ℂ
7170, 29pncan3oi 11517 . . . 4 ((2502 + 1) − 1) = 2502
7268, 71eqtr4i 2757 . . 3 (18 · 139) = ((2502 + 1) − 1)
7315, 72eqtr4i 2757 . 2 (𝑁 − 1) = (18 · 139)
7410, 18deccl 12738 . . . . . 6 2503 ∈ ℕ0
755, 74eqeltri 2822 . . . . 5 𝑁 ∈ ℕ0
7675nn0cni 12530 . . . 4 𝑁 ∈ ℂ
77 npcan 11510 . . . 4 ((𝑁 ∈ ℂ ∧ 1 ∈ ℂ) → ((𝑁 − 1) + 1) = 𝑁)
7876, 29, 77mp2an 690 . . 3 ((𝑁 − 1) + 1) = 𝑁
7978eqcomi 2735 . 2 𝑁 = ((𝑁 − 1) + 1)
80 1nn 12269 . 2 1 ∈ ℕ
81 2nn 12331 . 2 2 ∈ ℕ
8219, 20deccl 12738 . . . . 5 139 ∈ ℕ0
8382numexp1 17074 . . . 4 (139↑1) = 139
8483oveq2i 7427 . . 3 (18 · (139↑1)) = (18 · 139)
8573, 84eqtr4i 2757 . 2 (𝑁 − 1) = (18 · (139↑1))
86 8lt10 12855 . . . 4 8 < 10
87 1lt10 12862 . . . . 5 1 < 10
8880, 18, 2, 87declti 12761 . . . 4 1 < 13
892, 19, 16, 20, 86, 88decltc 12752 . . 3 18 < 139
9089, 83breqtrri 5172 . 2 18 < (139↑1)
9152503lem2 17135 . 2 ((2↑(𝑁 − 1)) mod 𝑁) = (1 mod 𝑁)
9252503lem3 17136 . 2 (((2↑18) − 1) gcd 𝑁) = 1
931, 4, 73, 79, 4, 80, 81, 85, 90, 91, 92pockthi 16904 1 𝑁 ∈ ℙ
Colors of variables: wff setvar class
Syntax hints:   = wceq 1534  wcel 2099  (class class class)co 7416  cc 11147  0cc0 11149  1c1 11150   + caddc 11152   · cmul 11154   < clt 11289  cmin 11485  2c2 12313  3c3 12314  4c4 12315  5c5 12316  6c6 12317  7c7 12318  8c8 12319  9c9 12320  0cn0 12518  cdc 12723  cexp 14075  cprime 16667
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1790  ax-4 1804  ax-5 1906  ax-6 1964  ax-7 2004  ax-8 2101  ax-9 2109  ax-10 2130  ax-11 2147  ax-12 2167  ax-ext 2697  ax-rep 5282  ax-sep 5296  ax-nul 5303  ax-pow 5361  ax-pr 5425  ax-un 7738  ax-cnex 11205  ax-resscn 11206  ax-1cn 11207  ax-icn 11208  ax-addcl 11209  ax-addrcl 11210  ax-mulcl 11211  ax-mulrcl 11212  ax-mulcom 11213  ax-addass 11214  ax-mulass 11215  ax-distr 11216  ax-i2m1 11217  ax-1ne0 11218  ax-1rid 11219  ax-rnegex 11220  ax-rrecex 11221  ax-cnre 11222  ax-pre-lttri 11223  ax-pre-lttrn 11224  ax-pre-ltadd 11225  ax-pre-mulgt0 11226  ax-pre-sup 11227
This theorem depends on definitions:  df-bi 206  df-an 395  df-or 846  df-3or 1085  df-3an 1086  df-tru 1537  df-fal 1547  df-ex 1775  df-nf 1779  df-sb 2061  df-mo 2529  df-eu 2558  df-clab 2704  df-cleq 2718  df-clel 2803  df-nfc 2878  df-ne 2931  df-nel 3037  df-ral 3052  df-rex 3061  df-rmo 3364  df-reu 3365  df-rab 3420  df-v 3464  df-sbc 3776  df-csb 3892  df-dif 3949  df-un 3951  df-in 3953  df-ss 3963  df-pss 3966  df-nul 4323  df-if 4524  df-pw 4599  df-sn 4624  df-pr 4626  df-op 4630  df-uni 4906  df-int 4947  df-iun 4995  df-br 5146  df-opab 5208  df-mpt 5229  df-tr 5263  df-id 5572  df-eprel 5578  df-po 5586  df-so 5587  df-fr 5629  df-we 5631  df-xp 5680  df-rel 5681  df-cnv 5682  df-co 5683  df-dm 5684  df-rn 5685  df-res 5686  df-ima 5687  df-pred 6304  df-ord 6371  df-on 6372  df-lim 6373  df-suc 6374  df-iota 6498  df-fun 6548  df-fn 6549  df-f 6550  df-f1 6551  df-fo 6552  df-f1o 6553  df-fv 6554  df-riota 7372  df-ov 7419  df-oprab 7420  df-mpo 7421  df-om 7869  df-1st 7995  df-2nd 7996  df-frecs 8288  df-wrecs 8319  df-recs 8393  df-rdg 8432  df-1o 8488  df-2o 8489  df-oadd 8492  df-er 8726  df-en 8967  df-dom 8968  df-sdom 8969  df-fin 8970  df-sup 9478  df-inf 9479  df-dju 9937  df-card 9975  df-pnf 11291  df-mnf 11292  df-xr 11293  df-ltxr 11294  df-le 11295  df-sub 11487  df-neg 11488  df-div 11913  df-nn 12259  df-2 12321  df-3 12322  df-4 12323  df-5 12324  df-6 12325  df-7 12326  df-8 12327  df-9 12328  df-n0 12519  df-xnn0 12591  df-z 12605  df-dec 12724  df-uz 12869  df-q 12979  df-rp 13023  df-fz 13533  df-fzo 13676  df-fl 13806  df-mod 13884  df-seq 14016  df-exp 14076  df-hash 14343  df-cj 15099  df-re 15100  df-im 15101  df-sqrt 15235  df-abs 15236  df-dvds 16252  df-gcd 16490  df-prm 16668  df-odz 16762  df-phi 16763  df-pc 16834
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator