# Proof for the divisibility of natural numbers by at least one prime

Like any other natural number, N is divisible by at least one prime number (it is possible that N itself is prime).

Is there a proof for this?

-
Note that this is true only for natural numbers $n>1$. – Brian M. Scott Jan 24 '13 at 2:50

Yes (modulo Brian's comment.)

Hint: Suppose not, and let $n$ be the least natural number $\ge 2$ that is not divisible by a prime. In particular, $n$ is not prime, so...

-

Hint $\$ If $n > 1$ then its least factor $> 1$ is prime. $\$ And similarly for polynomials:

$\qquad\ \$ if f(x) is nonconstant then its least-degree nonconstant factor is irreducible.

And similarly for Gaussian integers, by taking the least-norm nonunit factor, etc.

-

Let $P(n)$ be the statement, "$n$ is divisible by a prime number." Since 2 is prime and 2 divides itself, it follows that $P(2)$ is true. This serves as the based case of the induction. Let $m>2$ and assume that $P(k)$ is true for all $k$ where $2\le k<m.$ We would like to show that $P(m)$ is true. If $m$ is prime, then $m$ is divisible by a prime, namely itself, and hence $P(m)$ is true. If $m$ is not prime, then $m$ has a composite factor $b$ satisfying $2\le b<m$. By inductive hypothesis, $P(b)$ is true. This means that $b$ is divisible a prime number, say $p$. This implies that $p$ is a prime factor of $m$. Hence, $P(m)$ is true. Since $m>2$ was arbitrary, the result follows by Complete Induction.

-