# Proof: If no prime less than or equal to $\sqrt{n}$ divides $n$, then $n$ is a prime [duplicate]

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 StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); 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.

• Any integer, composite or not, which is greater than $1$ has prime factors. Is this not obvious to you? – Arthur Aug 14 '18 at 11:23
• @Arthur You're totally right. I never work with prime numbers, so this wasn't something that I was thinking of at all. – The Pointer Aug 14 '18 at 11:24
• @Arthur As this is a rather elementary proof, it feels wrong to presume knowledge like this. – Sudix Aug 14 '18 at 11:38
• @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. – Arthur Aug 14 '18 at 11:41
• @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) – Sudix Aug 14 '18 at 11:52

## 1 Answer

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.