Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
Note that this is true only for natural numbers $n>1$. –  Brian M. Scott Jan 24 '13 at 2:50
add comment

3 Answers

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.