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

Theorem pockthi 15989
Description: Pocklington's theorem, which gives a sufficient criterion for a number 𝑁 to be prime. This is the preferred method for verifying large primes, being much more efficient to compute than trial division. This form has been optimized for application to specific large primes; see pockthg 15988 for a more general closed-form version. (Contributed by Mario Carneiro, 2-Mar-2014.)
Hypotheses
Ref Expression
pockthi.p 𝑃 ∈ ℙ
pockthi.g 𝐺 ∈ ℕ
pockthi.m 𝑀 = (𝐺 · 𝑃)
pockthi.n 𝑁 = (𝑀 + 1)
pockthi.d 𝐷 ∈ ℕ
pockthi.e 𝐸 ∈ ℕ
pockthi.a 𝐴 ∈ ℕ
pockthi.fac 𝑀 = (𝐷 · (𝑃𝐸))
pockthi.gt 𝐷 < (𝑃𝐸)
pockthi.mod ((𝐴𝑀) mod 𝑁) = (1 mod 𝑁)
pockthi.gcd (((𝐴𝐺) − 1) gcd 𝑁) = 1
Assertion
Ref Expression
pockthi 𝑁 ∈ ℙ

Proof of Theorem pockthi
Dummy variables 𝑥 𝑦 are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 pockthi.d . 2 𝐷 ∈ ℕ
2 pockthi.p . . . . . 6 𝑃 ∈ ℙ
3 prmnn 15767 . . . . . 6 (𝑃 ∈ ℙ → 𝑃 ∈ ℕ)
42, 3ax-mp 5 . . . . 5 𝑃 ∈ ℕ
5 pockthi.e . . . . . 6 𝐸 ∈ ℕ
65nnnn0i 11634 . . . . 5 𝐸 ∈ ℕ0
7 nnexpcl 13174 . . . . 5 ((𝑃 ∈ ℕ ∧ 𝐸 ∈ ℕ0) → (𝑃𝐸) ∈ ℕ)
84, 6, 7mp2an 683 . . . 4 (𝑃𝐸) ∈ ℕ
98a1i 11 . . 3 (𝐷 ∈ ℕ → (𝑃𝐸) ∈ ℕ)
10 id 22 . . 3 (𝐷 ∈ ℕ → 𝐷 ∈ ℕ)
11 pockthi.gt . . . 4 𝐷 < (𝑃𝐸)
1211a1i 11 . . 3 (𝐷 ∈ ℕ → 𝐷 < (𝑃𝐸))
13 pockthi.n . . . . 5 𝑁 = (𝑀 + 1)
14 pockthi.fac . . . . . . 7 𝑀 = (𝐷 · (𝑃𝐸))
151nncni 11368 . . . . . . . 8 𝐷 ∈ ℂ
168nncni 11368 . . . . . . . 8 (𝑃𝐸) ∈ ℂ
1715, 16mulcomi 10372 . . . . . . 7 (𝐷 · (𝑃𝐸)) = ((𝑃𝐸) · 𝐷)
1814, 17eqtri 2849 . . . . . 6 𝑀 = ((𝑃𝐸) · 𝐷)
1918oveq1i 6920 . . . . 5 (𝑀 + 1) = (((𝑃𝐸) · 𝐷) + 1)
2013, 19eqtri 2849 . . . 4 𝑁 = (((𝑃𝐸) · 𝐷) + 1)
2120a1i 11 . . 3 (𝐷 ∈ ℕ → 𝑁 = (((𝑃𝐸) · 𝐷) + 1))
22 prmdvdsexpb 15806 . . . . . . 7 ((𝑥 ∈ ℙ ∧ 𝑃 ∈ ℙ ∧ 𝐸 ∈ ℕ) → (𝑥 ∥ (𝑃𝐸) ↔ 𝑥 = 𝑃))
232, 5, 22mp3an23 1581 . . . . . 6 (𝑥 ∈ ℙ → (𝑥 ∥ (𝑃𝐸) ↔ 𝑥 = 𝑃))
2413eqcomi 2834 . . . . . . . . . . 11 (𝑀 + 1) = 𝑁
25 pockthi.m . . . . . . . . . . . . . . . 16 𝑀 = (𝐺 · 𝑃)
26 pockthi.g . . . . . . . . . . . . . . . . 17 𝐺 ∈ ℕ
2726, 4nnmulcli 11384 . . . . . . . . . . . . . . . 16 (𝐺 · 𝑃) ∈ ℕ
2825, 27eqeltri 2902 . . . . . . . . . . . . . . 15 𝑀 ∈ ℕ
29 peano2nn 11371 . . . . . . . . . . . . . . 15 (𝑀 ∈ ℕ → (𝑀 + 1) ∈ ℕ)
3028, 29ax-mp 5 . . . . . . . . . . . . . 14 (𝑀 + 1) ∈ ℕ
3113, 30eqeltri 2902 . . . . . . . . . . . . 13 𝑁 ∈ ℕ
3231nncni 11368 . . . . . . . . . . . 12 𝑁 ∈ ℂ
33 ax-1cn 10317 . . . . . . . . . . . 12 1 ∈ ℂ
3428nncni 11368 . . . . . . . . . . . 12 𝑀 ∈ ℂ
3532, 33, 34subadd2i 10697 . . . . . . . . . . 11 ((𝑁 − 1) = 𝑀 ↔ (𝑀 + 1) = 𝑁)
3624, 35mpbir 223 . . . . . . . . . 10 (𝑁 − 1) = 𝑀
3736oveq2i 6921 . . . . . . . . 9 (𝐴↑(𝑁 − 1)) = (𝐴𝑀)
3837oveq1i 6920 . . . . . . . 8 ((𝐴↑(𝑁 − 1)) mod 𝑁) = ((𝐴𝑀) mod 𝑁)
39 pockthi.mod . . . . . . . . 9 ((𝐴𝑀) mod 𝑁) = (1 mod 𝑁)
4031nnrei 11367 . . . . . . . . . 10 𝑁 ∈ ℝ
4128nngt0i 11397 . . . . . . . . . . . 12 0 < 𝑀
4228nnrei 11367 . . . . . . . . . . . . 13 𝑀 ∈ ℝ
43 1re 10363 . . . . . . . . . . . . 13 1 ∈ ℝ
44 ltaddpos2 10850 . . . . . . . . . . . . 13 ((𝑀 ∈ ℝ ∧ 1 ∈ ℝ) → (0 < 𝑀 ↔ 1 < (𝑀 + 1)))
4542, 43, 44mp2an 683 . . . . . . . . . . . 12 (0 < 𝑀 ↔ 1 < (𝑀 + 1))
4641, 45mpbi 222 . . . . . . . . . . 11 1 < (𝑀 + 1)
4746, 13breqtrri 4902 . . . . . . . . . 10 1 < 𝑁
48 1mod 13004 . . . . . . . . . 10 ((𝑁 ∈ ℝ ∧ 1 < 𝑁) → (1 mod 𝑁) = 1)
4940, 47, 48mp2an 683 . . . . . . . . 9 (1 mod 𝑁) = 1
5039, 49eqtri 2849 . . . . . . . 8 ((𝐴𝑀) mod 𝑁) = 1
5138, 50eqtri 2849 . . . . . . 7 ((𝐴↑(𝑁 − 1)) mod 𝑁) = 1
52 oveq2 6918 . . . . . . . . . . . 12 (𝑥 = 𝑃 → ((𝑁 − 1) / 𝑥) = ((𝑁 − 1) / 𝑃))
5326nncni 11368 . . . . . . . . . . . . . . 15 𝐺 ∈ ℂ
544nncni 11368 . . . . . . . . . . . . . . 15 𝑃 ∈ ℂ
5553, 54mulcomi 10372 . . . . . . . . . . . . . 14 (𝐺 · 𝑃) = (𝑃 · 𝐺)
5636, 25, 553eqtrri 2854 . . . . . . . . . . . . 13 (𝑃 · 𝐺) = (𝑁 − 1)
5732, 33subcli 10685 . . . . . . . . . . . . . 14 (𝑁 − 1) ∈ ℂ
584nnne0i 11398 . . . . . . . . . . . . . 14 𝑃 ≠ 0
5957, 54, 53, 58divmuli 11112 . . . . . . . . . . . . 13 (((𝑁 − 1) / 𝑃) = 𝐺 ↔ (𝑃 · 𝐺) = (𝑁 − 1))
6056, 59mpbir 223 . . . . . . . . . . . 12 ((𝑁 − 1) / 𝑃) = 𝐺
6152, 60syl6eq 2877 . . . . . . . . . . 11 (𝑥 = 𝑃 → ((𝑁 − 1) / 𝑥) = 𝐺)
6261oveq2d 6926 . . . . . . . . . 10 (𝑥 = 𝑃 → (𝐴↑((𝑁 − 1) / 𝑥)) = (𝐴𝐺))
6362oveq1d 6925 . . . . . . . . 9 (𝑥 = 𝑃 → ((𝐴↑((𝑁 − 1) / 𝑥)) − 1) = ((𝐴𝐺) − 1))
6463oveq1d 6925 . . . . . . . 8 (𝑥 = 𝑃 → (((𝐴↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = (((𝐴𝐺) − 1) gcd 𝑁))
65 pockthi.gcd . . . . . . . 8 (((𝐴𝐺) − 1) gcd 𝑁) = 1
6664, 65syl6eq 2877 . . . . . . 7 (𝑥 = 𝑃 → (((𝐴↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1)
67 pockthi.a . . . . . . . . 9 𝐴 ∈ ℕ
6867nnzi 11736 . . . . . . . 8 𝐴 ∈ ℤ
69 oveq1 6917 . . . . . . . . . . . 12 (𝑦 = 𝐴 → (𝑦↑(𝑁 − 1)) = (𝐴↑(𝑁 − 1)))
7069oveq1d 6925 . . . . . . . . . . 11 (𝑦 = 𝐴 → ((𝑦↑(𝑁 − 1)) mod 𝑁) = ((𝐴↑(𝑁 − 1)) mod 𝑁))
7170eqeq1d 2827 . . . . . . . . . 10 (𝑦 = 𝐴 → (((𝑦↑(𝑁 − 1)) mod 𝑁) = 1 ↔ ((𝐴↑(𝑁 − 1)) mod 𝑁) = 1))
72 oveq1 6917 . . . . . . . . . . . . 13 (𝑦 = 𝐴 → (𝑦↑((𝑁 − 1) / 𝑥)) = (𝐴↑((𝑁 − 1) / 𝑥)))
7372oveq1d 6925 . . . . . . . . . . . 12 (𝑦 = 𝐴 → ((𝑦↑((𝑁 − 1) / 𝑥)) − 1) = ((𝐴↑((𝑁 − 1) / 𝑥)) − 1))
7473oveq1d 6925 . . . . . . . . . . 11 (𝑦 = 𝐴 → (((𝑦↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = (((𝐴↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁))
7574eqeq1d 2827 . . . . . . . . . 10 (𝑦 = 𝐴 → ((((𝑦↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1 ↔ (((𝐴↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1))
7671, 75anbi12d 624 . . . . . . . . 9 (𝑦 = 𝐴 → ((((𝑦↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑦↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1) ↔ (((𝐴↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝐴↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1)))
7776rspcev 3526 . . . . . . . 8 ((𝐴 ∈ ℤ ∧ (((𝐴↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝐴↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1)) → ∃𝑦 ∈ ℤ (((𝑦↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑦↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1))
7868, 77mpan 681 . . . . . . 7 ((((𝐴↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝐴↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1) → ∃𝑦 ∈ ℤ (((𝑦↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑦↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1))
7951, 66, 78sylancr 581 . . . . . 6 (𝑥 = 𝑃 → ∃𝑦 ∈ ℤ (((𝑦↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑦↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1))
8023, 79syl6bi 245 . . . . 5 (𝑥 ∈ ℙ → (𝑥 ∥ (𝑃𝐸) → ∃𝑦 ∈ ℤ (((𝑦↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑦↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1)))
8180rgen 3131 . . . 4 𝑥 ∈ ℙ (𝑥 ∥ (𝑃𝐸) → ∃𝑦 ∈ ℤ (((𝑦↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑦↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1))
8281a1i 11 . . 3 (𝐷 ∈ ℕ → ∀𝑥 ∈ ℙ (𝑥 ∥ (𝑃𝐸) → ∃𝑦 ∈ ℤ (((𝑦↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑦↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1)))
839, 10, 12, 21, 82pockthg 15988 . 2 (𝐷 ∈ ℕ → 𝑁 ∈ ℙ)
841, 83ax-mp 5 1 𝑁 ∈ ℙ
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 198  wa 386   = wceq 1656  wcel 2164  wral 3117  wrex 3118   class class class wbr 4875  (class class class)co 6910  cr 10258  0cc0 10259  1c1 10260   + caddc 10262   · cmul 10264   < clt 10398  cmin 10592   / cdiv 11016  cn 11357  0cn0 11625  cz 11711   mod cmo 12970  cexp 13161  cdvds 15364   gcd cgcd 15596  cprime 15764
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1894  ax-4 1908  ax-5 2009  ax-6 2075  ax-7 2112  ax-8 2166  ax-9 2173  ax-10 2192  ax-11 2207  ax-12 2220  ax-13 2389  ax-ext 2803  ax-rep 4996  ax-sep 5007  ax-nul 5015  ax-pow 5067  ax-pr 5129  ax-un 7214  ax-cnex 10315  ax-resscn 10316  ax-1cn 10317  ax-icn 10318  ax-addcl 10319  ax-addrcl 10320  ax-mulcl 10321  ax-mulrcl 10322  ax-mulcom 10323  ax-addass 10324  ax-mulass 10325  ax-distr 10326  ax-i2m1 10327  ax-1ne0 10328  ax-1rid 10329  ax-rnegex 10330  ax-rrecex 10331  ax-cnre 10332  ax-pre-lttri 10333  ax-pre-lttrn 10334  ax-pre-ltadd 10335  ax-pre-mulgt0 10336  ax-pre-sup 10337
This theorem depends on definitions:  df-bi 199  df-an 387  df-or 879  df-3or 1112  df-3an 1113  df-tru 1660  df-ex 1879  df-nf 1883  df-sb 2068  df-mo 2605  df-eu 2640  df-clab 2812  df-cleq 2818  df-clel 2821  df-nfc 2958  df-ne 3000  df-nel 3103  df-ral 3122  df-rex 3123  df-reu 3124  df-rmo 3125  df-rab 3126  df-v 3416  df-sbc 3663  df-csb 3758  df-dif 3801  df-un 3803  df-in 3805  df-ss 3812  df-pss 3814  df-nul 4147  df-if 4309  df-pw 4382  df-sn 4400  df-pr 4402  df-tp 4404  df-op 4406  df-uni 4661  df-int 4700  df-iun 4744  df-br 4876  df-opab 4938  df-mpt 4955  df-tr 4978  df-id 5252  df-eprel 5257  df-po 5265  df-so 5266  df-fr 5305  df-we 5307  df-xp 5352  df-rel 5353  df-cnv 5354  df-co 5355  df-dm 5356  df-rn 5357  df-res 5358  df-ima 5359  df-pred 5924  df-ord 5970  df-on 5971  df-lim 5972  df-suc 5973  df-iota 6090  df-fun 6129  df-fn 6130  df-f 6131  df-f1 6132  df-fo 6133  df-f1o 6134  df-fv 6135  df-riota 6871  df-ov 6913  df-oprab 6914  df-mpt2 6915  df-om 7332  df-1st 7433  df-2nd 7434  df-wrecs 7677  df-recs 7739  df-rdg 7777  df-1o 7831  df-2o 7832  df-oadd 7835  df-er 8014  df-map 8129  df-en 8229  df-dom 8230  df-sdom 8231  df-fin 8232  df-sup 8623  df-inf 8624  df-card 9085  df-cda 9312  df-pnf 10400  df-mnf 10401  df-xr 10402  df-ltxr 10403  df-le 10404  df-sub 10594  df-neg 10595  df-div 11017  df-nn 11358  df-2 11421  df-3 11422  df-n0 11626  df-xnn0 11698  df-z 11712  df-uz 11976  df-q 12079  df-rp 12120  df-fz 12627  df-fzo 12768  df-fl 12895  df-mod 12971  df-seq 13103  df-exp 13162  df-hash 13418  df-cj 14223  df-re 14224  df-im 14225  df-sqrt 14359  df-abs 14360  df-dvds 15365  df-gcd 15597  df-prm 15765  df-odz 15848  df-phi 15849  df-pc 15920
This theorem is referenced by:  1259prm  16215  2503prm  16219  4001prm  16224
  Copyright terms: Public domain W3C validator