Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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...

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.