Definition D1
b | a means that a natural number k exists satisfying a = bk.
Proof.
This renders divisor 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.
1 is excluded by this definition, since p > 1 is required.convention
∎
Lemma L1
If p is prime and p | ab, then p | a or p | b.
Proof.
(1)Suppose p ∤ a. We show p | b.assumption
(2)The only divisors of p are 1 and p, so gcd(p, a) is 1 or p.D2, D1
(3)If gcd(p, a) = p then p | a, so gcd(p, a) = 1.(1), (2), D1
(4)There are integers x, y with 1 = px + ay.A3, (3)
(5)b = b × 1 = (px + ay)bA6, E, (4)
(6) = (bp)x + (ab)yA7, A4, A5
(7)(bp)x = p(bx), so p | (bp)x.A4, A5, D1
(8)Writing ab = pc, we get (ab)y = p(cy), so p | (ab)y.assumption, D1, A4
(9)b = p(bx) + p(cy) = p(bx + cy)(6), (7), (8), A7
(10)Therefore p | b.(9), D1
∎
Theorem T1
Every natural number greater than 1 is a product of primes.
Proof.
(1)Let S be the set of all natural numbers greater than 1 that cannot be written as a product of primes.convention
(2)Suppose S ≠ ∅.assumption
(3)S has a least element m.A2
(4)If m is prime, then m is a product of one prime, so m ∉ S.D2, (1)
(5)Therefore m is not prime, and m = ab with a neither 1 nor m.D2, D1, (4)
(6)If b = 1 then m = a, so b ≠ 1.A6, (5)
(7)Since 1 < a and 1 < b, a < ab = m and b < m.A1, A6, A8, (5), (6)
(8)a and b are greater than 1 and less than m, so they do not belong to S.(3), (7)
(9)Therefore a and b are each products of primes.(8), (1)
(10)Then m = ab is also a product of primes. This contradicts (3).(9), (5), (1)
(11)Therefore S = ∅.(10)
∎
Theorem T2
That product is unique up to order.
Proof.
(1)Let S be the set of all natural numbers greater than 1 that can be written as products of primes in two ways.convention
(2)Suppose S ≠ ∅, and let m be its least element.assumption, A2
(3)Write m = p₁p₂⋯p_r = q₁q₂⋯q_s.(1)
(4)p₁ | q₁q₂⋯q_s.(3), A4, A5, D1
(5)Applying L1 repeatedly, p₁ | q_j for some j.L1, (4)
(6)q_j is prime and p₁ > 1, so p₁ = q_j.D2, (5)
(7)Since p₁ > 1, cancelling p₁ from both sides makes p₂⋯p_r equal to the product with q_j removed.(3), (6), A4, A5, A9
(8)If that value is 1, no primes remain on either side, so both expressions are p₁ alone.(7), (6)
(9)If that value is greater than 1, it is less than m and so does not belong to S.(7), (2), A1, A6, A8
(10)Therefore the two expressions in (7) agree up to order.(9), (1)
(11)Restoring p₁ = q_j, the two expressions of m also agree up to order.(10), (6)
(12)This contradicts m ∈ S. Therefore S = ∅.(11), (1)
∎