Each integer
\[n \ge 2\]
is divisible by a prime number.Proof
\[P(2), \; P(3)\]
, the statements that 2, 3 are divisible by primes are true, since 2 and 3 are prime numbers.Suppose that
\[(4), \; P(5),..., P(k-1), \; P(k)\]
are true, so that each of \[4, \; 5, ..., k-1, \; k\]
; is divisible by a prime number. We must probe \[P(k+1)\]
is true. Either \[k+1\]
is prime or it is composite. If it is [prime then it is divisible by itself, which is prime. If it is composite then \[k+1=rs, 2 \lt \; r, \; s \lt k\]
. The induction hypothesis now implies \[, r, \; s\]
are both divisible by some prime, and this prime also divides \[k+1\]
.