Every natural number greater than 1 is divisible by a prime number

Question

Sorry if this question has been asked, but a couldn't find one using the method I need.

I want to prove that every natural number greater than 1 is divisible by some prime number using the WOP. I have done this by taking S to be the set of natural numbers greater than 1 which aren't divisible by a prime. But my notes now say to do it by taking S to be the set of all factors of n which are greater than 1.

Any help would be appreciated. Thanks.

$S$ is not empty ($n \in S$), so it has a smallest element, let's call it $p$. Now argue that $p$ is a prime. — Daniel Fischer, Dec 12 '13 at 13:09

score 1 · Accepted Answer · answered Dec 12 '13 at 13:10

1

Take $S$ to be the set of non-$1$ factors of $n$. By the WOP, there is a smallest one, say $n_0$. Then $n_0$ has no divisors except for $1$ and $n_0$ itself, because any divisor of $n_0$ would be a divisor of $n$.

So, $n_0$ is a...

answered Dec 12 '13 at 13:10

rewritten

3,092

I know it's an old question but to complete the proof we also have to argue that in case $n_0$ is a not a prime then it has a set of factors $S_1$ and by WOP it has a least element ... correct? – Dec 21 '19 at 13:35

Every natural number greater than 1 is divisible by a prime number

1 Answers1