Lemma·L20
Every number above one has a prime divisor
Factor out the smallest piece: a prime always divides.
In words
For every n, if n is a natural number greater than one then there is some p that is prime and divides n.
Never needed: F05 · F10 · F13 · A02 · A03 · A04 · A05 · A07 (computed from the citation graph, not asserted).
Proof
- 1We apply strong induction to (Separation). So let , assume every lies in , and assume ; we must produce a prime divisor of .
- 2Case prime: take ; then by L19 (i).
- 3Case not prime: since , the failure of primality means some has with and (negation of the universal clause, excluded middle).
- 4The divisor is strictly between: first : indeed (L15 (vi) at ) and give by transitivity (L15 (ii)), so by irreflexivity (L15 (i)). Next : otherwise (witness from D030, Claim A of L11), contradiction. From : (L15 (iv) with trichotomy), so (L15 (v)); as , we get . Finally by L19 (vii) (using ), and gives .
- 5
∎
Remarks
The archetype of a strong-induction argument: the divisor
produced by non-primality is smaller than
but nowhere near its predecessor, so ordinary induction has no grip, while strong induction descends effortlessly. Iterating the lemma (divide by the prime, repeat) is the existence half of the fundamental theorem of arithmetic; here it is the supplier of primes for Euclid's theorem.