0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Note that this is true only for natural numbers $n>1$. $\endgroup$ Jan 24, 2013 at 2:50

3 Answers 3

2
$\begingroup$

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...

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .