Definition D1
b | a means that a natural number k exists satisfying a = bk.
Proof.
This renders 'b is a divisor of a' as a single multiplication.convention
∎
Definition D2
p is prime means that p > 1 and the only divisors of p are 1 and p.
Proof.
There are two conditions: greater than 1, and no divisors besides those two.convention
∎
Lemma L1
If p | a and a | m, then p | m
Proof.
(1)There are k, l with a = pk and m = al.assumption, D1
(2)m = (pk)l(1), E
(3) = p(kl)A4
(4)Therefore p | m.(3), D1
∎
Lemma L2
Every natural number greater than 1 has a prime divisor.
Proof.
(1)Let S be the set of all natural numbers greater than 1 with no prime factor.convention
(2)Suppose S ≠ ∅.assumption
(3)S has a least element m.A2
(4)Since m = m × 1, m | m.A6, D1
(5)If m were prime, then by (4) m would be a prime factor of m, so m ∉ S.D2, (4), (1)
(6)Therefore m is not prime, and has a divisor a that is neither 1 nor m.D2, (5)
(7)There is a k with m = ak, and since a ≠ m, k ≠ 1.(6), D1, A6
(8)Since 1 ≤ k, we have 1 < k, and a = a × 1 ≤ ak = m.(7), A1, A6, A7
(9)a is neither 1 nor m, so 1 < a < m.(6), (8), A1
(10)Since m is the least element of S, a ∉ S. That is, a has a prime factor p.(3), (9), (1)
(11)Since p | a and a | m, p | m.(10), L1
(12)m has a prime factor, so m ∉ S. This contradicts (3).(11), (1)
(13)Therefore S = ∅.(12)
∎
Theorem T
There are infinitely many primes.
Proof.
(1)Suppose the primes are finite in number, and let them all be p₁, p₂, …, pₙ.assumption
(2)Set P = p₁p₂⋯pₙ and N = P + 1.convention
(3)For each i, P can be grouped as pᵢ times the product of the remaining primes.A4, A5
(4)Therefore there is a t with P = pᵢ t, and pᵢ | P.(3), D1
(5)N = pᵢ t + 1, and since pᵢ > 1, 0 ≤ 1 < pᵢ.(2), (4), D2
(6)Quotient and remainder are unique, so the remainder of N divided by pᵢ is 1.A3, (5)
(7)If pᵢ | N, then N = pᵢ s + 0, so the remainder is 0.D1, A3
(8)Since 1 ≠ 0, no pᵢ divides N.(6), (7)
(9)Since 1 ≤ P, N = P + 1 > 1.A1, (2)
(10)Therefore N has a prime factor q.(9), L2
(11)Since q | N, by (8) q is not equal to any pᵢ.(10), (8)
(12)q is a prime not on the list in (1). This contradicts (1).(11), (1)
(13)Therefore the primes are not finite in number.(12)
∎