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.

  • 1
    $\begingroup$ $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. $\endgroup$ – Daniel Fischer Dec 12 '13 at 13:09

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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