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

Theorem prmlem1a 16431
 Description: A quick proof skeleton to show that the numbers less than 25 are prime, by trial division. (Contributed by Mario Carneiro, 18-Feb-2014.)
Hypotheses
Ref Expression
prmlem1.n 𝑁 ∈ ℕ
prmlem1.gt 1 < 𝑁
prmlem1.2 ¬ 2 ∥ 𝑁
prmlem1.3 ¬ 3 ∥ 𝑁
prmlem1a.x ((¬ 2 ∥ 5 ∧ 𝑥 ∈ (ℤ‘5)) → ((𝑥 ∈ (ℙ ∖ {2}) ∧ (𝑥↑2) ≤ 𝑁) → ¬ 𝑥𝑁))
Assertion
Ref Expression
prmlem1a 𝑁 ∈ ℙ
Distinct variable group:   𝑥,𝑁

Proof of Theorem prmlem1a
StepHypRef Expression
1 prmlem1.n . . 3 𝑁 ∈ ℕ
2 prmlem1.gt . . 3 1 < 𝑁
3 eluz2b2 12309 . . 3 (𝑁 ∈ (ℤ‘2) ↔ (𝑁 ∈ ℕ ∧ 1 < 𝑁))
41, 2, 3mpbir2an 710 . 2 𝑁 ∈ (ℤ‘2)
5 breq1 5052 . . . . . 6 (𝑥 = 2 → (𝑥𝑁 ↔ 2 ∥ 𝑁))
65notbid 321 . . . . 5 (𝑥 = 2 → (¬ 𝑥𝑁 ↔ ¬ 2 ∥ 𝑁))
76imbi2d 344 . . . 4 (𝑥 = 2 → (((𝑥↑2) ≤ 𝑁 → ¬ 𝑥𝑁) ↔ ((𝑥↑2) ≤ 𝑁 → ¬ 2 ∥ 𝑁)))
8 prmnn 16007 . . . . . 6 (𝑥 ∈ ℙ → 𝑥 ∈ ℕ)
98adantr 484 . . . . 5 ((𝑥 ∈ ℙ ∧ 𝑥 ≠ 2) → 𝑥 ∈ ℕ)
10 eldifsn 4702 . . . . . 6 (𝑥 ∈ (ℙ ∖ {2}) ↔ (𝑥 ∈ ℙ ∧ 𝑥 ≠ 2))
11 n2dvds1 15708 . . . . . . . . 9 ¬ 2 ∥ 1
12 prmlem1a.x . . . . . . . . . . 11 ((¬ 2 ∥ 5 ∧ 𝑥 ∈ (ℤ‘5)) → ((𝑥 ∈ (ℙ ∖ {2}) ∧ (𝑥↑2) ≤ 𝑁) → ¬ 𝑥𝑁))
13 prmlem1.3 . . . . . . . . . . . 12 ¬ 3 ∥ 𝑁
1413a1i 11 . . . . . . . . . . 11 (3 ∈ ℙ → ¬ 3 ∥ 𝑁)
15 3p2e5 11776 . . . . . . . . . . 11 (3 + 2) = 5
1612, 14, 15prmlem0 16430 . . . . . . . . . 10 ((¬ 2 ∥ 3 ∧ 𝑥 ∈ (ℤ‘3)) → ((𝑥 ∈ (ℙ ∖ {2}) ∧ (𝑥↑2) ≤ 𝑁) → ¬ 𝑥𝑁))
17 1nprm 16012 . . . . . . . . . . 11 ¬ 1 ∈ ℙ
1817pm2.21i 119 . . . . . . . . . 10 (1 ∈ ℙ → ¬ 1 ∥ 𝑁)
19 1p2e3 11768 . . . . . . . . . 10 (1 + 2) = 3
2016, 18, 19prmlem0 16430 . . . . . . . . 9 ((¬ 2 ∥ 1 ∧ 𝑥 ∈ (ℤ‘1)) → ((𝑥 ∈ (ℙ ∖ {2}) ∧ (𝑥↑2) ≤ 𝑁) → ¬ 𝑥𝑁))
2111, 20mpan 689 . . . . . . . 8 (𝑥 ∈ (ℤ‘1) → ((𝑥 ∈ (ℙ ∖ {2}) ∧ (𝑥↑2) ≤ 𝑁) → ¬ 𝑥𝑁))
22 nnuz 12269 . . . . . . . 8 ℕ = (ℤ‘1)
2321, 22eleq2s 2934 . . . . . . 7 (𝑥 ∈ ℕ → ((𝑥 ∈ (ℙ ∖ {2}) ∧ (𝑥↑2) ≤ 𝑁) → ¬ 𝑥𝑁))
2423expd 419 . . . . . 6 (𝑥 ∈ ℕ → (𝑥 ∈ (ℙ ∖ {2}) → ((𝑥↑2) ≤ 𝑁 → ¬ 𝑥𝑁)))
2510, 24syl5bir 246 . . . . 5 (𝑥 ∈ ℕ → ((𝑥 ∈ ℙ ∧ 𝑥 ≠ 2) → ((𝑥↑2) ≤ 𝑁 → ¬ 𝑥𝑁)))
269, 25mpcom 38 . . . 4 ((𝑥 ∈ ℙ ∧ 𝑥 ≠ 2) → ((𝑥↑2) ≤ 𝑁 → ¬ 𝑥𝑁))
27 prmlem1.2 . . . . 5 ¬ 2 ∥ 𝑁
28272a1i 12 . . . 4 (𝑥 ∈ ℙ → ((𝑥↑2) ≤ 𝑁 → ¬ 2 ∥ 𝑁))
297, 26, 28pm2.61ne 3098 . . 3 (𝑥 ∈ ℙ → ((𝑥↑2) ≤ 𝑁 → ¬ 𝑥𝑁))
3029rgen 3142 . 2 𝑥 ∈ ℙ ((𝑥↑2) ≤ 𝑁 → ¬ 𝑥𝑁)
31 isprm5 16040 . 2 (𝑁 ∈ ℙ ↔ (𝑁 ∈ (ℤ‘2) ∧ ∀𝑥 ∈ ℙ ((𝑥↑2) ≤ 𝑁 → ¬ 𝑥𝑁)))
324, 30, 31mpbir2an 710 1 𝑁 ∈ ℙ
 Colors of variables: wff setvar class Syntax hints:  ¬ wn 3   → wi 4   ∧ wa 399   = wceq 1538   ∈ wcel 2115   ≠ wne 3013  ∀wral 3132   ∖ cdif 3915  {csn 4548   class class class wbr 5049  ‘cfv 6338  (class class class)co 7140  1c1 10525   < clt 10662   ≤ cle 10663  ℕcn 11625  2c2 11680  3c3 11681  5c5 11683  ℤ≥cuz 12231  ↑cexp 13425   ∥ cdvds 15598  ℙcprime 16004 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1797  ax-4 1811  ax-5 1912  ax-6 1971  ax-7 2016  ax-8 2117  ax-9 2125  ax-10 2146  ax-11 2162  ax-12 2179  ax-ext 2796  ax-sep 5186  ax-nul 5193  ax-pow 5249  ax-pr 5313  ax-un 7446  ax-cnex 10580  ax-resscn 10581  ax-1cn 10582  ax-icn 10583  ax-addcl 10584  ax-addrcl 10585  ax-mulcl 10586  ax-mulrcl 10587  ax-mulcom 10588  ax-addass 10589  ax-mulass 10590  ax-distr 10591  ax-i2m1 10592  ax-1ne0 10593  ax-1rid 10594  ax-rnegex 10595  ax-rrecex 10596  ax-cnre 10597  ax-pre-lttri 10598  ax-pre-lttrn 10599  ax-pre-ltadd 10600  ax-pre-mulgt0 10601  ax-pre-sup 10602 This theorem depends on definitions:  df-bi 210  df-an 400  df-or 845  df-3or 1085  df-3an 1086  df-tru 1541  df-ex 1782  df-nf 1786  df-sb 2071  df-mo 2624  df-eu 2655  df-clab 2803  df-cleq 2817  df-clel 2896  df-nfc 2964  df-ne 3014  df-nel 3118  df-ral 3137  df-rex 3138  df-reu 3139  df-rmo 3140  df-rab 3141  df-v 3481  df-sbc 3758  df-csb 3866  df-dif 3921  df-un 3923  df-in 3925  df-ss 3935  df-pss 3937  df-nul 4275  df-if 4449  df-pw 4522  df-sn 4549  df-pr 4551  df-tp 4553  df-op 4555  df-uni 4822  df-iun 4904  df-br 5050  df-opab 5112  df-mpt 5130  df-tr 5156  df-id 5443  df-eprel 5448  df-po 5457  df-so 5458  df-fr 5497  df-we 5499  df-xp 5544  df-rel 5545  df-cnv 5546  df-co 5547  df-dm 5548  df-rn 5549  df-res 5550  df-ima 5551  df-pred 6131  df-ord 6177  df-on 6178  df-lim 6179  df-suc 6180  df-iota 6297  df-fun 6340  df-fn 6341  df-f 6342  df-f1 6343  df-fo 6344  df-f1o 6345  df-fv 6346  df-riota 7098  df-ov 7143  df-oprab 7144  df-mpo 7145  df-om 7566  df-1st 7674  df-2nd 7675  df-wrecs 7932  df-recs 7993  df-rdg 8031  df-1o 8087  df-2o 8088  df-er 8274  df-en 8495  df-dom 8496  df-sdom 8497  df-fin 8498  df-sup 8892  df-pnf 10664  df-mnf 10665  df-xr 10666  df-ltxr 10667  df-le 10668  df-sub 10859  df-neg 10860  df-div 11285  df-nn 11626  df-2 11688  df-3 11689  df-4 11690  df-5 11691  df-n0 11886  df-z 11970  df-uz 12232  df-rp 12378  df-fz 12886  df-seq 13365  df-exp 13426  df-cj 14449  df-re 14450  df-im 14451  df-sqrt 14585  df-abs 14586  df-dvds 15599  df-prm 16005 This theorem is referenced by:  prmlem1  16432  prmlem2  16444
 Copyright terms: Public domain W3C validator