Definition D1
b | a means there exists a natural number k with a = bk.
Proof.
This restates 'b is a divisor of a' using a single multiplication.convention
∎
Definition D2
That p is prime means p > 1 and the only divisors of p are 1 and p.
Proof.
There are two conditions: being greater than 1, and having only those two divisors.convention
∎
Definition D3
That n is composite means n > 1 and n is not prime.
Proof.
1 is not composite. The condition of being greater than 1 rules it out.convention, D2
∎
Definition D4
√n is the nonnegative x satisfying x × x = n, and for a natural number p, p ≤ √n and p × p ≤ n are the same condition.
Proof.
From here on we write p × p ≤ n without the radical.convention
∎
Lemma L1
If n is composite, there are natural numbers a, b with n = ab and 1 < a ≤ b.
Proof.
(1)n is greater than 1 and not prime.assumption, D3
(2)There is a divisor c that is neither 1 nor n.(1), D2
(3)There is d with n = cd.(2), D1
(4)1 ≤ c and c ≠ 1, so 1 < c.(2), A1, A4
(5)If d = 1, then n = c × 1 = c, contradicting c ≠ n.(2), (3), A8
(6)1 ≤ d and d ≠ 1, so 1 < d.(5), A1, A4
(7)If c ≤ d, set a = c, b = d; otherwise set a = d, b = c.A3, A4
(8)In either case n = ab and 1 < a ≤ b.(3), (4), (6), (7), A6
∎
Lemma L2
If p is a divisor of a, then p ≤ a
Proof.
(1)There is k with a = pk.assumption, D1
(2)1 ≤ kA1
(3)1 × p ≤ k × p(2), A5
(4)1 × p = p and k × p = pk = a(1), A6, A8
(5)Therefore p ≤ a.(3), (4), E
∎
Theorem T
A composite number n has a prime factor p with p × p ≤ n.
Proof.
(1)There are a, b with n = ab and 1 < a ≤ b.L1
(2)Suppose n < a × a.assumption
(3)a ≤ b, so a × a ≤ b × a.(1), A5
(4)b × a = ab = n(1), A6
(5)Therefore a × a ≤ n.(3), (4), E
(6)n < a × a and a × a ≤ n cannot stand together.(2), (5), A4, A3
(7)Therefore a × a ≤ n.(6), A3, A4
(8)1 < a, so a has a prime factor p.(1), A9
(9)p ≤ a(8), L2
(10)p × p ≤ a × p and a × p = p × a ≤ a × a.(9), A5, A6
(11)p × p ≤ a × a(10), A2
(12)p × p ≤ n(11), (7), A2
(13)a = pk and n = ab = (pk)b = p(kb), so p | n.(1), (8), D1, A7
(14)p is a prime factor of n and p × p ≤ n.(12), (13), D2
∎
Corollary C
If n > 1 and no prime p with p × p ≤ n divides n, then n is prime.
Proof.
(1)Suppose such an n is not prime.assumption
(2)n is greater than 1 and not prime, hence composite.(1), D3
(3)n has a prime factor p with p × p ≤ n.(2), T
(4)This contradicts the hypothesis.(1), (3)
(5)Therefore n is prime.(4), D2
(6)The only primes to check are those with p × p ≤ n, that is, p ≤ √n.(5), D4
∎