This question already has an answer here:

I have the following theorem:

If no prime less than or equal to $\sqrt{n}$ divides $n$, then $n$ is a prime.

And the following proof (proof by contradiction) for said theorem:

Suppose that no prime less than or equal to $\sqrt{n}$ divides $n$ but $n = ab$, with neither $a$ nor $b$ equal to $1$.

Now $a$ and $b$ cannot both be strictly larger than $\sqrt{n}$ or their product would be larger than $n$.

So one of $a$ or $b$ is not larger than $\sqrt{n}$: assume (without loss of generality) that $a \le \sqrt{n}$.

Now $a$ cannot be prime (as we have assumed $n$ has no prime factor this small), and so is composite.

Therefore $a$ has a prime factor $p$, which must be less than $a$.

But then $p < a \le \sqrt{n}$ is a prime factor of $n$, and this contradicts our hypothesis.

Hence $n$ is prime.

We deduce that $a$ is composite. But why does this then mean that $a$ has a prime factor $p$? So this is saying that all composite numbers have a prime factor? Why?

I would greatly appreciate it if people could please take the time to clarify this.

PostScript: I am assuming that this is the definition of composite number being used here.


marked as duplicate by lab bhattacharjee elementary-number-theory Aug 14 '18 at 11:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Any integer, composite or not, which is greater than $1$ has prime factors. Is this not obvious to you? $\endgroup$ – Arthur Aug 14 '18 at 11:23
  • $\begingroup$ @Arthur You're totally right. I never work with prime numbers, so this wasn't something that I was thinking of at all. $\endgroup$ – The Pointer Aug 14 '18 at 11:24
  • $\begingroup$ @Arthur As this is a rather elementary proof, it feels wrong to presume knowledge like this. $\endgroup$ – Sudix Aug 14 '18 at 11:38
  • $\begingroup$ @Sudix Maybe. It's not very difficult to prove, though. The smallest divisor $a$ (apart from $1$) of any given natural number $n>1$ has to be prime because the divisors of $a$ will also be divisors of $n$, and $n$ has no divisors smaller than $a$, so $a$ can't have any divisors smaller than $a$ either. $\endgroup$ – Arthur Aug 14 '18 at 11:41
  • $\begingroup$ @Arthur True, it's not difficult to prove once you know the general proof techniques to reach your aim. I would have used infinite descend, but your proof fits in with the proof above a lot more nicely. Let's hope OP takes the time to integrate your proof into the one above, because that way he gets a satisfying answer to his question (unlike in the answer that's linked, or the answer below) $\endgroup$ – Sudix Aug 14 '18 at 11:52

We have assumed $a>1$ (See the first line) and we have show it cannot be prime (otherwise $n$ has a prime factor $\leq\sqrt n$).

Typically, the definition of composite is that the number can be written as the product of more than one prime (that is, is greater than $1$ and isn’t prime). This follows from the Fundamental Theorem of Arithmetic.


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