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

Theorem pockthi 15392
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 15391 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 15169 . . . . . 6 (𝑃 ∈ ℙ → 𝑃 ∈ ℕ)
42, 3ax-mp 5 . . . . 5 𝑃 ∈ ℕ
5 pockthi.e . . . . . 6 𝐸 ∈ ℕ
65nnnn0i 11144 . . . . 5 𝐸 ∈ ℕ0
7 nnexpcl 12687 . . . . 5 ((𝑃 ∈ ℕ ∧ 𝐸 ∈ ℕ0) → (𝑃𝐸) ∈ ℕ)
84, 6, 7mp2an 703 . . . 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 10874 . . . . . . . 8 𝐷 ∈ ℂ
168nncni 10874 . . . . . . . 8 (𝑃𝐸) ∈ ℂ
1715, 16mulcomi 9899 . . . . . . 7 (𝐷 · (𝑃𝐸)) = ((𝑃𝐸) · 𝐷)
1814, 17eqtri 2628 . . . . . 6 𝑀 = ((𝑃𝐸) · 𝐷)
1918oveq1i 6534 . . . . 5 (𝑀 + 1) = (((𝑃𝐸) · 𝐷) + 1)
2013, 19eqtri 2628 . . . 4 𝑁 = (((𝑃𝐸) · 𝐷) + 1)
2120a1i 11 . . 3 (𝐷 ∈ ℕ → 𝑁 = (((𝑃𝐸) · 𝐷) + 1))
22 prmdvdsexpb 15209 . . . . . . 7 ((𝑥 ∈ ℙ ∧ 𝑃 ∈ ℙ ∧ 𝐸 ∈ ℕ) → (𝑥 ∥ (𝑃𝐸) ↔ 𝑥 = 𝑃))
232, 5, 22mp3an23 1407 . . . . . 6 (𝑥 ∈ ℙ → (𝑥 ∥ (𝑃𝐸) ↔ 𝑥 = 𝑃))
2413eqcomi 2615 . . . . . . . . . . 11 (𝑀 + 1) = 𝑁
25 pockthi.m . . . . . . . . . . . . . . . 16 𝑀 = (𝐺 · 𝑃)
26 pockthi.g . . . . . . . . . . . . . . . . 17 𝐺 ∈ ℕ
2726, 4nnmulcli 10888 . . . . . . . . . . . . . . . 16 (𝐺 · 𝑃) ∈ ℕ
2825, 27eqeltri 2680 . . . . . . . . . . . . . . 15 𝑀 ∈ ℕ
29 peano2nn 10876 . . . . . . . . . . . . . . 15 (𝑀 ∈ ℕ → (𝑀 + 1) ∈ ℕ)
3028, 29ax-mp 5 . . . . . . . . . . . . . 14 (𝑀 + 1) ∈ ℕ
3113, 30eqeltri 2680 . . . . . . . . . . . . 13 𝑁 ∈ ℕ
3231nncni 10874 . . . . . . . . . . . 12 𝑁 ∈ ℂ
33 ax-1cn 9847 . . . . . . . . . . . 12 1 ∈ ℂ
3428nncni 10874 . . . . . . . . . . . 12 𝑀 ∈ ℂ
3532, 33, 34subadd2i 10217 . . . . . . . . . . 11 ((𝑁 − 1) = 𝑀 ↔ (𝑀 + 1) = 𝑁)
3624, 35mpbir 219 . . . . . . . . . 10 (𝑁 − 1) = 𝑀
3736oveq2i 6535 . . . . . . . . 9 (𝐴↑(𝑁 − 1)) = (𝐴𝑀)
3837oveq1i 6534 . . . . . . . 8 ((𝐴↑(𝑁 − 1)) mod 𝑁) = ((𝐴𝑀) mod 𝑁)
39 pockthi.mod . . . . . . . . 9 ((𝐴𝑀) mod 𝑁) = (1 mod 𝑁)
4031nnrei 10873 . . . . . . . . . 10 𝑁 ∈ ℝ
4128nngt0i 10898 . . . . . . . . . . . 12 0 < 𝑀
4228nnrei 10873 . . . . . . . . . . . . 13 𝑀 ∈ ℝ
43 1re 9892 . . . . . . . . . . . . 13 1 ∈ ℝ
44 ltaddpos2 10365 . . . . . . . . . . . . 13 ((𝑀 ∈ ℝ ∧ 1 ∈ ℝ) → (0 < 𝑀 ↔ 1 < (𝑀 + 1)))
4542, 43, 44mp2an 703 . . . . . . . . . . . 12 (0 < 𝑀 ↔ 1 < (𝑀 + 1))
4641, 45mpbi 218 . . . . . . . . . . 11 1 < (𝑀 + 1)
4746, 13breqtrri 4601 . . . . . . . . . 10 1 < 𝑁
48 1mod 12516 . . . . . . . . . 10 ((𝑁 ∈ ℝ ∧ 1 < 𝑁) → (1 mod 𝑁) = 1)
4940, 47, 48mp2an 703 . . . . . . . . 9 (1 mod 𝑁) = 1
5039, 49eqtri 2628 . . . . . . . 8 ((𝐴𝑀) mod 𝑁) = 1
5138, 50eqtri 2628 . . . . . . 7 ((𝐴↑(𝑁 − 1)) mod 𝑁) = 1
52 oveq2 6532 . . . . . . . . . . . 12 (𝑥 = 𝑃 → ((𝑁 − 1) / 𝑥) = ((𝑁 − 1) / 𝑃))
5326nncni 10874 . . . . . . . . . . . . . . 15 𝐺 ∈ ℂ
544nncni 10874 . . . . . . . . . . . . . . 15 𝑃 ∈ ℂ
5553, 54mulcomi 9899 . . . . . . . . . . . . . 14 (𝐺 · 𝑃) = (𝑃 · 𝐺)
5636, 25, 553eqtrri 2633 . . . . . . . . . . . . 13 (𝑃 · 𝐺) = (𝑁 − 1)
5732, 33subcli 10205 . . . . . . . . . . . . . 14 (𝑁 − 1) ∈ ℂ
584nnne0i 10899 . . . . . . . . . . . . . 14 𝑃 ≠ 0
5957, 54, 53, 58divmuli 10625 . . . . . . . . . . . . 13 (((𝑁 − 1) / 𝑃) = 𝐺 ↔ (𝑃 · 𝐺) = (𝑁 − 1))
6056, 59mpbir 219 . . . . . . . . . . . 12 ((𝑁 − 1) / 𝑃) = 𝐺
6152, 60syl6eq 2656 . . . . . . . . . . 11 (𝑥 = 𝑃 → ((𝑁 − 1) / 𝑥) = 𝐺)
6261oveq2d 6540 . . . . . . . . . 10 (𝑥 = 𝑃 → (𝐴↑((𝑁 − 1) / 𝑥)) = (𝐴𝐺))
6362oveq1d 6539 . . . . . . . . 9 (𝑥 = 𝑃 → ((𝐴↑((𝑁 − 1) / 𝑥)) − 1) = ((𝐴𝐺) − 1))
6463oveq1d 6539 . . . . . . . 8 (𝑥 = 𝑃 → (((𝐴↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = (((𝐴𝐺) − 1) gcd 𝑁))
65 pockthi.gcd . . . . . . . 8 (((𝐴𝐺) − 1) gcd 𝑁) = 1
6664, 65syl6eq 2656 . . . . . . 7 (𝑥 = 𝑃 → (((𝐴↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1)
67 pockthi.a . . . . . . . . 9 𝐴 ∈ ℕ
6867nnzi 11231 . . . . . . . 8 𝐴 ∈ ℤ
69 oveq1 6531 . . . . . . . . . . . 12 (𝑦 = 𝐴 → (𝑦↑(𝑁 − 1)) = (𝐴↑(𝑁 − 1)))
7069oveq1d 6539 . . . . . . . . . . 11 (𝑦 = 𝐴 → ((𝑦↑(𝑁 − 1)) mod 𝑁) = ((𝐴↑(𝑁 − 1)) mod 𝑁))
7170eqeq1d 2608 . . . . . . . . . 10 (𝑦 = 𝐴 → (((𝑦↑(𝑁 − 1)) mod 𝑁) = 1 ↔ ((𝐴↑(𝑁 − 1)) mod 𝑁) = 1))
72 oveq1 6531 . . . . . . . . . . . . 13 (𝑦 = 𝐴 → (𝑦↑((𝑁 − 1) / 𝑥)) = (𝐴↑((𝑁 − 1) / 𝑥)))
7372oveq1d 6539 . . . . . . . . . . . 12 (𝑦 = 𝐴 → ((𝑦↑((𝑁 − 1) / 𝑥)) − 1) = ((𝐴↑((𝑁 − 1) / 𝑥)) − 1))
7473oveq1d 6539 . . . . . . . . . . 11 (𝑦 = 𝐴 → (((𝑦↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = (((𝐴↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁))
7574eqeq1d 2608 . . . . . . . . . 10 (𝑦 = 𝐴 → ((((𝑦↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1 ↔ (((𝐴↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1))
7671, 75anbi12d 742 . . . . . . . . 9 (𝑦 = 𝐴 → ((((𝑦↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑦↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1) ↔ (((𝐴↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝐴↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1)))
7776rspcev 3278 . . . . . . . 8 ((𝐴 ∈ ℤ ∧ (((𝐴↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝐴↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1)) → ∃𝑦 ∈ ℤ (((𝑦↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑦↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1))
7868, 77mpan 701 . . . . . . 7 ((((𝐴↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝐴↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1) → ∃𝑦 ∈ ℤ (((𝑦↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑦↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1))
7951, 66, 78sylancr 693 . . . . . 6 (𝑥 = 𝑃 → ∃𝑦 ∈ ℤ (((𝑦↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑦↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1))
8023, 79syl6bi 241 . . . . 5 (𝑥 ∈ ℙ → (𝑥 ∥ (𝑃𝐸) → ∃𝑦 ∈ ℤ (((𝑦↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑦↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1)))
8180rgen 2902 . . . 4 𝑥 ∈ ℙ (𝑥 ∥ (𝑃𝐸) → ∃𝑦 ∈ ℤ (((𝑦↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑦↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1))
8281a1i 11 . . 3 (𝐷 ∈ ℕ → ∀𝑥 ∈ ℙ (𝑥 ∥ (𝑃𝐸) → ∃𝑦 ∈ ℤ (((𝑦↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑦↑((𝑁 − 1) / 𝑥)) − 1) gcd 𝑁) = 1)))
839, 10, 12, 21, 82pockthg 15391 . 2 (𝐷 ∈ ℕ → 𝑁 ∈ ℙ)
841, 83ax-mp 5 1 𝑁 ∈ ℙ
Colors of variables: wff setvar class
Syntax hints:  wi 4  wb 194  wa 382   = wceq 1474  wcel 1976  wral 2892  wrex 2893   class class class wbr 4574  (class class class)co 6524  cr 9788  0cc0 9789  1c1 9790   + caddc 9792   · cmul 9794   < clt 9927  cmin 10114   / cdiv 10530  cn 10864  0cn0 11136  cz 11207   mod cmo 12482  cexp 12674  cdvds 14764   gcd cgcd 14997  cprime 15166
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1712  ax-4 1727  ax-5 1826  ax-6 1874  ax-7 1921  ax-8 1978  ax-9 1985  ax-10 2005  ax-11 2020  ax-12 2032  ax-13 2229  ax-ext 2586  ax-rep 4690  ax-sep 4700  ax-nul 4709  ax-pow 4761  ax-pr 4825  ax-un 6821  ax-cnex 9845  ax-resscn 9846  ax-1cn 9847  ax-icn 9848  ax-addcl 9849  ax-addrcl 9850  ax-mulcl 9851  ax-mulrcl 9852  ax-mulcom 9853  ax-addass 9854  ax-mulass 9855  ax-distr 9856  ax-i2m1 9857  ax-1ne0 9858  ax-1rid 9859  ax-rnegex 9860  ax-rrecex 9861  ax-cnre 9862  ax-pre-lttri 9863  ax-pre-lttrn 9864  ax-pre-ltadd 9865  ax-pre-mulgt0 9866  ax-pre-sup 9867
This theorem depends on definitions:  df-bi 195  df-or 383  df-an 384  df-3or 1031  df-3an 1032  df-tru 1477  df-ex 1695  df-nf 1700  df-sb 1867  df-eu 2458  df-mo 2459  df-clab 2593  df-cleq 2599  df-clel 2602  df-nfc 2736  df-ne 2778  df-nel 2779  df-ral 2897  df-rex 2898  df-reu 2899  df-rmo 2900  df-rab 2901  df-v 3171  df-sbc 3399  df-csb 3496  df-dif 3539  df-un 3541  df-in 3543  df-ss 3550  df-pss 3552  df-nul 3871  df-if 4033  df-pw 4106  df-sn 4122  df-pr 4124  df-tp 4126  df-op 4128  df-uni 4364  df-int 4402  df-iun 4448  df-br 4575  df-opab 4635  df-mpt 4636  df-tr 4672  df-eprel 4936  df-id 4940  df-po 4946  df-so 4947  df-fr 4984  df-we 4986  df-xp 5031  df-rel 5032  df-cnv 5033  df-co 5034  df-dm 5035  df-rn 5036  df-res 5037  df-ima 5038  df-pred 5580  df-ord 5626  df-on 5627  df-lim 5628  df-suc 5629  df-iota 5751  df-fun 5789  df-fn 5790  df-f 5791  df-f1 5792  df-fo 5793  df-f1o 5794  df-fv 5795  df-riota 6486  df-ov 6527  df-oprab 6528  df-mpt2 6529  df-om 6932  df-1st 7033  df-2nd 7034  df-wrecs 7268  df-recs 7329  df-rdg 7367  df-1o 7421  df-2o 7422  df-oadd 7425  df-er 7603  df-map 7720  df-en 7816  df-dom 7817  df-sdom 7818  df-fin 7819  df-sup 8205  df-inf 8206  df-card 8622  df-cda 8847  df-pnf 9929  df-mnf 9930  df-xr 9931  df-ltxr 9932  df-le 9933  df-sub 10116  df-neg 10117  df-div 10531  df-nn 10865  df-2 10923  df-3 10924  df-n0 11137  df-z 11208  df-uz 11517  df-q 11618  df-rp 11662  df-fz 12150  df-fzo 12287  df-fl 12407  df-mod 12483  df-seq 12616  df-exp 12675  df-hash 12932  df-cj 13630  df-re 13631  df-im 13632  df-sqrt 13766  df-abs 13767  df-dvds 14765  df-gcd 14998  df-prm 15167  df-odz 15251  df-phi 15252  df-pc 15323
This theorem is referenced by:  1259prm  15624  2503prm  15628  4001prm  15633
  Copyright terms: Public domain W3C validator