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

Theorem pockthg 15827
Description: The generalized Pocklington's theorem. If 𝑁 − 1 = 𝐴 · 𝐵 where 𝐵 < 𝐴, then 𝑁 is prime if and only if for every prime factor 𝑝 of 𝐴, there is an 𝑥 such that 𝑥↑(𝑁 − 1) = 1( mod 𝑁) and gcd (𝑥↑((𝑁 − 1) / 𝑝) − 1, 𝑁) = 1. (Contributed by Mario Carneiro, 2-Mar-2014.)
Hypotheses
Ref Expression
pockthg.1 (𝜑𝐴 ∈ ℕ)
pockthg.2 (𝜑𝐵 ∈ ℕ)
pockthg.3 (𝜑𝐵 < 𝐴)
pockthg.4 (𝜑𝑁 = ((𝐴 · 𝐵) + 1))
pockthg.5 (𝜑 → ∀𝑝 ∈ ℙ (𝑝𝐴 → ∃𝑥 ∈ ℤ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1)))
Assertion
Ref Expression
pockthg (𝜑𝑁 ∈ ℙ)
Distinct variable groups:   𝑥,𝑝,𝑁   𝐴,𝑝,𝑥   𝜑,𝑝,𝑥
Allowed substitution hints:   𝐵(𝑥,𝑝)

Proof of Theorem pockthg
Dummy variable 𝑞 is distinct from all other variables.
StepHypRef Expression
1 pockthg.4 . . 3 (𝜑𝑁 = ((𝐴 · 𝐵) + 1))
2 pockthg.1 . . . . . . 7 (𝜑𝐴 ∈ ℕ)
3 pockthg.2 . . . . . . 7 (𝜑𝐵 ∈ ℕ)
42, 3nnmulcld 11354 . . . . . 6 (𝜑 → (𝐴 · 𝐵) ∈ ℕ)
5 nnuz 11941 . . . . . 6 ℕ = (ℤ‘1)
64, 5syl6eleq 2895 . . . . 5 (𝜑 → (𝐴 · 𝐵) ∈ (ℤ‘1))
7 eluzp1p1 11930 . . . . 5 ((𝐴 · 𝐵) ∈ (ℤ‘1) → ((𝐴 · 𝐵) + 1) ∈ (ℤ‘(1 + 1)))
86, 7syl 17 . . . 4 (𝜑 → ((𝐴 · 𝐵) + 1) ∈ (ℤ‘(1 + 1)))
9 df-2 11364 . . . . 5 2 = (1 + 1)
109fveq2i 6411 . . . 4 (ℤ‘2) = (ℤ‘(1 + 1))
118, 10syl6eleqr 2896 . . 3 (𝜑 → ((𝐴 · 𝐵) + 1) ∈ (ℤ‘2))
121, 11eqeltrd 2885 . 2 (𝜑𝑁 ∈ (ℤ‘2))
13 eluzelre 11915 . . . . . . . . 9 (𝑁 ∈ (ℤ‘2) → 𝑁 ∈ ℝ)
1412, 13syl 17 . . . . . . . 8 (𝜑𝑁 ∈ ℝ)
1514adantr 468 . . . . . . 7 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → 𝑁 ∈ ℝ)
162nnred 11320 . . . . . . . . 9 (𝜑𝐴 ∈ ℝ)
1716resqcld 13258 . . . . . . . 8 (𝜑 → (𝐴↑2) ∈ ℝ)
1817adantr 468 . . . . . . 7 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → (𝐴↑2) ∈ ℝ)
19 prmnn 15606 . . . . . . . . . 10 (𝑞 ∈ ℙ → 𝑞 ∈ ℕ)
2019ad2antrl 710 . . . . . . . . 9 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → 𝑞 ∈ ℕ)
2120nnred 11320 . . . . . . . 8 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → 𝑞 ∈ ℝ)
2221resqcld 13258 . . . . . . 7 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → (𝑞↑2) ∈ ℝ)
23 pockthg.3 . . . . . . . . . . 11 (𝜑𝐵 < 𝐴)
243nnred 11320 . . . . . . . . . . . 12 (𝜑𝐵 ∈ ℝ)
252nngt0d 11350 . . . . . . . . . . . 12 (𝜑 → 0 < 𝐴)
26 ltmul2 11159 . . . . . . . . . . . 12 ((𝐵 ∈ ℝ ∧ 𝐴 ∈ ℝ ∧ (𝐴 ∈ ℝ ∧ 0 < 𝐴)) → (𝐵 < 𝐴 ↔ (𝐴 · 𝐵) < (𝐴 · 𝐴)))
2724, 16, 16, 25, 26syl112anc 1486 . . . . . . . . . . 11 (𝜑 → (𝐵 < 𝐴 ↔ (𝐴 · 𝐵) < (𝐴 · 𝐴)))
2823, 27mpbid 223 . . . . . . . . . 10 (𝜑 → (𝐴 · 𝐵) < (𝐴 · 𝐴))
292, 2nnmulcld 11354 . . . . . . . . . . 11 (𝜑 → (𝐴 · 𝐴) ∈ ℕ)
30 nnltp1le 11699 . . . . . . . . . . 11 (((𝐴 · 𝐵) ∈ ℕ ∧ (𝐴 · 𝐴) ∈ ℕ) → ((𝐴 · 𝐵) < (𝐴 · 𝐴) ↔ ((𝐴 · 𝐵) + 1) ≤ (𝐴 · 𝐴)))
314, 29, 30syl2anc 575 . . . . . . . . . 10 (𝜑 → ((𝐴 · 𝐵) < (𝐴 · 𝐴) ↔ ((𝐴 · 𝐵) + 1) ≤ (𝐴 · 𝐴)))
3228, 31mpbid 223 . . . . . . . . 9 (𝜑 → ((𝐴 · 𝐵) + 1) ≤ (𝐴 · 𝐴))
332nncnd 11321 . . . . . . . . . 10 (𝜑𝐴 ∈ ℂ)
3433sqvald 13228 . . . . . . . . 9 (𝜑 → (𝐴↑2) = (𝐴 · 𝐴))
3532, 1, 343brtr4d 4876 . . . . . . . 8 (𝜑𝑁 ≤ (𝐴↑2))
3635adantr 468 . . . . . . 7 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → 𝑁 ≤ (𝐴↑2))
37 pockthg.5 . . . . . . . . . . . . 13 (𝜑 → ∀𝑝 ∈ ℙ (𝑝𝐴 → ∃𝑥 ∈ ℤ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1)))
3837adantr 468 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → ∀𝑝 ∈ ℙ (𝑝𝐴 → ∃𝑥 ∈ ℤ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1)))
39 prmnn 15606 . . . . . . . . . . . . . . . . . . . 20 (𝑝 ∈ ℙ → 𝑝 ∈ ℕ)
4039ad2antrl 710 . . . . . . . . . . . . . . . . . . 19 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) → 𝑝 ∈ ℕ)
4140nncnd 11321 . . . . . . . . . . . . . . . . . 18 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) → 𝑝 ∈ ℂ)
4241exp1d 13226 . . . . . . . . . . . . . . . . 17 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) → (𝑝↑1) = 𝑝)
43 nnge1 11332 . . . . . . . . . . . . . . . . . . 19 ((𝑝 pCnt 𝐴) ∈ ℕ → 1 ≤ (𝑝 pCnt 𝐴))
4443ad2antll 711 . . . . . . . . . . . . . . . . . 18 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) → 1 ≤ (𝑝 pCnt 𝐴))
45 simprl 778 . . . . . . . . . . . . . . . . . . 19 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) → 𝑝 ∈ ℙ)
462nnzd 11747 . . . . . . . . . . . . . . . . . . . 20 (𝜑𝐴 ∈ ℤ)
4746ad2antrr 708 . . . . . . . . . . . . . . . . . . 19 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) → 𝐴 ∈ ℤ)
48 1nn0 11575 . . . . . . . . . . . . . . . . . . . 20 1 ∈ ℕ0
4948a1i 11 . . . . . . . . . . . . . . . . . . 19 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) → 1 ∈ ℕ0)
50 pcdvdsb 15790 . . . . . . . . . . . . . . . . . . 19 ((𝑝 ∈ ℙ ∧ 𝐴 ∈ ℤ ∧ 1 ∈ ℕ0) → (1 ≤ (𝑝 pCnt 𝐴) ↔ (𝑝↑1) ∥ 𝐴))
5145, 47, 49, 50syl3anc 1483 . . . . . . . . . . . . . . . . . 18 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) → (1 ≤ (𝑝 pCnt 𝐴) ↔ (𝑝↑1) ∥ 𝐴))
5244, 51mpbid 223 . . . . . . . . . . . . . . . . 17 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) → (𝑝↑1) ∥ 𝐴)
5342, 52eqbrtrrd 4868 . . . . . . . . . . . . . . . 16 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) → 𝑝𝐴)
54 simpl1 1235 . . . . . . . . . . . . . . . . . . . 20 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) ∧ (𝑥 ∈ ℤ ∧ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1))) → 𝜑)
5554, 2syl 17 . . . . . . . . . . . . . . . . . . 19 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) ∧ (𝑥 ∈ ℤ ∧ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1))) → 𝐴 ∈ ℕ)
5654, 3syl 17 . . . . . . . . . . . . . . . . . . 19 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) ∧ (𝑥 ∈ ℤ ∧ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1))) → 𝐵 ∈ ℕ)
5754, 23syl 17 . . . . . . . . . . . . . . . . . . 19 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) ∧ (𝑥 ∈ ℤ ∧ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1))) → 𝐵 < 𝐴)
5854, 1syl 17 . . . . . . . . . . . . . . . . . . 19 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) ∧ (𝑥 ∈ ℤ ∧ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1))) → 𝑁 = ((𝐴 · 𝐵) + 1))
59 simpl2l 1290 . . . . . . . . . . . . . . . . . . 19 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) ∧ (𝑥 ∈ ℤ ∧ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1))) → 𝑞 ∈ ℙ)
60 simpl2r 1292 . . . . . . . . . . . . . . . . . . 19 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) ∧ (𝑥 ∈ ℤ ∧ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1))) → 𝑞𝑁)
61 simpl3l 1294 . . . . . . . . . . . . . . . . . . 19 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) ∧ (𝑥 ∈ ℤ ∧ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1))) → 𝑝 ∈ ℙ)
62 simpl3r 1296 . . . . . . . . . . . . . . . . . . 19 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) ∧ (𝑥 ∈ ℤ ∧ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1))) → (𝑝 pCnt 𝐴) ∈ ℕ)
63 simprl 778 . . . . . . . . . . . . . . . . . . 19 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) ∧ (𝑥 ∈ ℤ ∧ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1))) → 𝑥 ∈ ℤ)
64 simprrl 790 . . . . . . . . . . . . . . . . . . 19 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) ∧ (𝑥 ∈ ℤ ∧ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1))) → ((𝑥↑(𝑁 − 1)) mod 𝑁) = 1)
65 simprrr 791 . . . . . . . . . . . . . . . . . . 19 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) ∧ (𝑥 ∈ ℤ ∧ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1))) → (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1)
6655, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65pockthlem 15826 . . . . . . . . . . . . . . . . . 18 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) ∧ (𝑥 ∈ ℤ ∧ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1))) → (𝑝 pCnt 𝐴) ≤ (𝑝 pCnt (𝑞 − 1)))
6766rexlimdvaa 3220 . . . . . . . . . . . . . . . . 17 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) → (∃𝑥 ∈ ℤ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1) → (𝑝 pCnt 𝐴) ≤ (𝑝 pCnt (𝑞 − 1))))
68673expa 1140 . . . . . . . . . . . . . . . 16 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) → (∃𝑥 ∈ ℤ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1) → (𝑝 pCnt 𝐴) ≤ (𝑝 pCnt (𝑞 − 1))))
6953, 68embantd 59 . . . . . . . . . . . . . . 15 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ (𝑝 ∈ ℙ ∧ (𝑝 pCnt 𝐴) ∈ ℕ)) → ((𝑝𝐴 → ∃𝑥 ∈ ℤ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1)) → (𝑝 pCnt 𝐴) ≤ (𝑝 pCnt (𝑞 − 1))))
7069expr 446 . . . . . . . . . . . . . 14 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ 𝑝 ∈ ℙ) → ((𝑝 pCnt 𝐴) ∈ ℕ → ((𝑝𝐴 → ∃𝑥 ∈ ℤ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1)) → (𝑝 pCnt 𝐴) ≤ (𝑝 pCnt (𝑞 − 1)))))
71 id 22 . . . . . . . . . . . . . . . . . 18 (𝑝 ∈ ℙ → 𝑝 ∈ ℙ)
72 prmuz2 15626 . . . . . . . . . . . . . . . . . . . 20 (𝑞 ∈ ℙ → 𝑞 ∈ (ℤ‘2))
73 uz2m1nn 11982 . . . . . . . . . . . . . . . . . . . 20 (𝑞 ∈ (ℤ‘2) → (𝑞 − 1) ∈ ℕ)
7472, 73syl 17 . . . . . . . . . . . . . . . . . . 19 (𝑞 ∈ ℙ → (𝑞 − 1) ∈ ℕ)
7574ad2antrl 710 . . . . . . . . . . . . . . . . . 18 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → (𝑞 − 1) ∈ ℕ)
76 pccl 15771 . . . . . . . . . . . . . . . . . 18 ((𝑝 ∈ ℙ ∧ (𝑞 − 1) ∈ ℕ) → (𝑝 pCnt (𝑞 − 1)) ∈ ℕ0)
7771, 75, 76syl2anr 586 . . . . . . . . . . . . . . . . 17 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ 𝑝 ∈ ℙ) → (𝑝 pCnt (𝑞 − 1)) ∈ ℕ0)
7877nn0ge0d 11620 . . . . . . . . . . . . . . . 16 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ 𝑝 ∈ ℙ) → 0 ≤ (𝑝 pCnt (𝑞 − 1)))
79 breq1 4847 . . . . . . . . . . . . . . . 16 ((𝑝 pCnt 𝐴) = 0 → ((𝑝 pCnt 𝐴) ≤ (𝑝 pCnt (𝑞 − 1)) ↔ 0 ≤ (𝑝 pCnt (𝑞 − 1))))
8078, 79syl5ibrcom 238 . . . . . . . . . . . . . . 15 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ 𝑝 ∈ ℙ) → ((𝑝 pCnt 𝐴) = 0 → (𝑝 pCnt 𝐴) ≤ (𝑝 pCnt (𝑞 − 1))))
8180a1dd 50 . . . . . . . . . . . . . 14 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ 𝑝 ∈ ℙ) → ((𝑝 pCnt 𝐴) = 0 → ((𝑝𝐴 → ∃𝑥 ∈ ℤ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1)) → (𝑝 pCnt 𝐴) ≤ (𝑝 pCnt (𝑞 − 1)))))
82 simpr 473 . . . . . . . . . . . . . . . 16 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ 𝑝 ∈ ℙ) → 𝑝 ∈ ℙ)
832ad2antrr 708 . . . . . . . . . . . . . . . 16 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ 𝑝 ∈ ℙ) → 𝐴 ∈ ℕ)
8482, 83pccld 15772 . . . . . . . . . . . . . . 15 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ 𝑝 ∈ ℙ) → (𝑝 pCnt 𝐴) ∈ ℕ0)
85 elnn0 11561 . . . . . . . . . . . . . . 15 ((𝑝 pCnt 𝐴) ∈ ℕ0 ↔ ((𝑝 pCnt 𝐴) ∈ ℕ ∨ (𝑝 pCnt 𝐴) = 0))
8684, 85sylib 209 . . . . . . . . . . . . . 14 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ 𝑝 ∈ ℙ) → ((𝑝 pCnt 𝐴) ∈ ℕ ∨ (𝑝 pCnt 𝐴) = 0))
8770, 81, 86mpjaod 878 . . . . . . . . . . . . 13 (((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) ∧ 𝑝 ∈ ℙ) → ((𝑝𝐴 → ∃𝑥 ∈ ℤ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1)) → (𝑝 pCnt 𝐴) ≤ (𝑝 pCnt (𝑞 − 1))))
8887ralimdva 3150 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → (∀𝑝 ∈ ℙ (𝑝𝐴 → ∃𝑥 ∈ ℤ (((𝑥↑(𝑁 − 1)) mod 𝑁) = 1 ∧ (((𝑥↑((𝑁 − 1) / 𝑝)) − 1) gcd 𝑁) = 1)) → ∀𝑝 ∈ ℙ (𝑝 pCnt 𝐴) ≤ (𝑝 pCnt (𝑞 − 1))))
8938, 88mpd 15 . . . . . . . . . . 11 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → ∀𝑝 ∈ ℙ (𝑝 pCnt 𝐴) ≤ (𝑝 pCnt (𝑞 − 1)))
9046adantr 468 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → 𝐴 ∈ ℤ)
9175nnzd 11747 . . . . . . . . . . . 12 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → (𝑞 − 1) ∈ ℤ)
92 pc2dvds 15800 . . . . . . . . . . . 12 ((𝐴 ∈ ℤ ∧ (𝑞 − 1) ∈ ℤ) → (𝐴 ∥ (𝑞 − 1) ↔ ∀𝑝 ∈ ℙ (𝑝 pCnt 𝐴) ≤ (𝑝 pCnt (𝑞 − 1))))
9390, 91, 92syl2anc 575 . . . . . . . . . . 11 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → (𝐴 ∥ (𝑞 − 1) ↔ ∀𝑝 ∈ ℙ (𝑝 pCnt 𝐴) ≤ (𝑝 pCnt (𝑞 − 1))))
9489, 93mpbird 248 . . . . . . . . . 10 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → 𝐴 ∥ (𝑞 − 1))
95 dvdsle 15255 . . . . . . . . . . 11 ((𝐴 ∈ ℤ ∧ (𝑞 − 1) ∈ ℕ) → (𝐴 ∥ (𝑞 − 1) → 𝐴 ≤ (𝑞 − 1)))
9690, 75, 95syl2anc 575 . . . . . . . . . 10 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → (𝐴 ∥ (𝑞 − 1) → 𝐴 ≤ (𝑞 − 1)))
9794, 96mpd 15 . . . . . . . . 9 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → 𝐴 ≤ (𝑞 − 1))
982nnnn0d 11617 . . . . . . . . . . 11 (𝜑𝐴 ∈ ℕ0)
9998adantr 468 . . . . . . . . . 10 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → 𝐴 ∈ ℕ0)
10020nnnn0d 11617 . . . . . . . . . 10 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → 𝑞 ∈ ℕ0)
101 nn0ltlem1 11703 . . . . . . . . . 10 ((𝐴 ∈ ℕ0𝑞 ∈ ℕ0) → (𝐴 < 𝑞𝐴 ≤ (𝑞 − 1)))
10299, 100, 101syl2anc 575 . . . . . . . . 9 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → (𝐴 < 𝑞𝐴 ≤ (𝑞 − 1)))
10397, 102mpbird 248 . . . . . . . 8 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → 𝐴 < 𝑞)
10416adantr 468 . . . . . . . . 9 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → 𝐴 ∈ ℝ)
10598nn0ge0d 11620 . . . . . . . . . 10 (𝜑 → 0 ≤ 𝐴)
106105adantr 468 . . . . . . . . 9 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → 0 ≤ 𝐴)
107100nn0ge0d 11620 . . . . . . . . 9 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → 0 ≤ 𝑞)
108104, 21, 106, 107lt2sqd 13266 . . . . . . . 8 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → (𝐴 < 𝑞 ↔ (𝐴↑2) < (𝑞↑2)))
109103, 108mpbid 223 . . . . . . 7 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → (𝐴↑2) < (𝑞↑2))
11015, 18, 22, 36, 109lelttrd 10480 . . . . . 6 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → 𝑁 < (𝑞↑2))
11115, 22ltnled 10469 . . . . . 6 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → (𝑁 < (𝑞↑2) ↔ ¬ (𝑞↑2) ≤ 𝑁))
112110, 111mpbid 223 . . . . 5 ((𝜑 ∧ (𝑞 ∈ ℙ ∧ 𝑞𝑁)) → ¬ (𝑞↑2) ≤ 𝑁)
113112expr 446 . . . 4 ((𝜑𝑞 ∈ ℙ) → (𝑞𝑁 → ¬ (𝑞↑2) ≤ 𝑁))
114113con2d 131 . . 3 ((𝜑𝑞 ∈ ℙ) → ((𝑞↑2) ≤ 𝑁 → ¬ 𝑞𝑁))
115114ralrimiva 3154 . 2 (𝜑 → ∀𝑞 ∈ ℙ ((𝑞↑2) ≤ 𝑁 → ¬ 𝑞𝑁))
116 isprm5 15636 . 2 (𝑁 ∈ ℙ ↔ (𝑁 ∈ (ℤ‘2) ∧ ∀𝑞 ∈ ℙ ((𝑞↑2) ≤ 𝑁 → ¬ 𝑞𝑁)))
11712, 115, 116sylanbrc 574 1 (𝜑𝑁 ∈ ℙ)
Colors of variables: wff setvar class
Syntax hints:  ¬ wn 3  wi 4  wb 197  wa 384  wo 865  w3a 1100   = wceq 1637  wcel 2156  wral 3096  wrex 3097   class class class wbr 4844  cfv 6101  (class class class)co 6874  cr 10220  0cc0 10221  1c1 10222   + caddc 10224   · cmul 10226   < clt 10359  cle 10360  cmin 10551   / cdiv 10969  cn 11305  2c2 11356  0cn0 11559  cz 11643  cuz 11904   mod cmo 12892  cexp 13083  cdvds 15203   gcd cgcd 15435  cprime 15603   pCnt cpc 15758
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1877  ax-4 1894  ax-5 2001  ax-6 2068  ax-7 2104  ax-8 2158  ax-9 2165  ax-10 2185  ax-11 2201  ax-12 2214  ax-13 2420  ax-ext 2784  ax-rep 4964  ax-sep 4975  ax-nul 4983  ax-pow 5035  ax-pr 5096  ax-un 7179  ax-cnex 10277  ax-resscn 10278  ax-1cn 10279  ax-icn 10280  ax-addcl 10281  ax-addrcl 10282  ax-mulcl 10283  ax-mulrcl 10284  ax-mulcom 10285  ax-addass 10286  ax-mulass 10287  ax-distr 10288  ax-i2m1 10289  ax-1ne0 10290  ax-1rid 10291  ax-rnegex 10292  ax-rrecex 10293  ax-cnre 10294  ax-pre-lttri 10295  ax-pre-lttrn 10296  ax-pre-ltadd 10297  ax-pre-mulgt0 10298  ax-pre-sup 10299
This theorem depends on definitions:  df-bi 198  df-an 385  df-or 866  df-3or 1101  df-3an 1102  df-tru 1641  df-ex 1860  df-nf 1864  df-sb 2061  df-eu 2634  df-mo 2635  df-clab 2793  df-cleq 2799  df-clel 2802  df-nfc 2937  df-ne 2979  df-nel 3082  df-ral 3101  df-rex 3102  df-reu 3103  df-rmo 3104  df-rab 3105  df-v 3393  df-sbc 3634  df-csb 3729  df-dif 3772  df-un 3774  df-in 3776  df-ss 3783  df-pss 3785  df-nul 4117  df-if 4280  df-pw 4353  df-sn 4371  df-pr 4373  df-tp 4375  df-op 4377  df-uni 4631  df-int 4670  df-iun 4714  df-br 4845  df-opab 4907  df-mpt 4924  df-tr 4947  df-id 5219  df-eprel 5224  df-po 5232  df-so 5233  df-fr 5270  df-we 5272  df-xp 5317  df-rel 5318  df-cnv 5319  df-co 5320  df-dm 5321  df-rn 5322  df-res 5323  df-ima 5324  df-pred 5893  df-ord 5939  df-on 5940  df-lim 5941  df-suc 5942  df-iota 6064  df-fun 6103  df-fn 6104  df-f 6105  df-f1 6106  df-fo 6107  df-f1o 6108  df-fv 6109  df-riota 6835  df-ov 6877  df-oprab 6878  df-mpt2 6879  df-om 7296  df-1st 7398  df-2nd 7399  df-wrecs 7642  df-recs 7704  df-rdg 7742  df-1o 7796  df-2o 7797  df-oadd 7800  df-er 7979  df-map 8094  df-en 8193  df-dom 8194  df-sdom 8195  df-fin 8196  df-sup 8587  df-inf 8588  df-card 9048  df-cda 9275  df-pnf 10361  df-mnf 10362  df-xr 10363  df-ltxr 10364  df-le 10365  df-sub 10553  df-neg 10554  df-div 10970  df-nn 11306  df-2 11364  df-3 11365  df-n0 11560  df-xnn0 11630  df-z 11644  df-uz 11905  df-q 12008  df-rp 12047  df-fz 12550  df-fzo 12690  df-fl 12817  df-mod 12893  df-seq 13025  df-exp 13084  df-hash 13338  df-cj 14062  df-re 14063  df-im 14064  df-sqrt 14198  df-abs 14199  df-dvds 15204  df-gcd 15436  df-prm 15604  df-odz 15687  df-phi 15688  df-pc 15759
This theorem is referenced by:  pockthi  15828  proththd  42106
  Copyright terms: Public domain W3C validator