# How would one prove that $\sqrt{n}$ is the largest divisor that needs to be checked to determine if $n$ is prime?

Prove the statement:

$\forall n \in \mathbb{N}$,$\forall m \in \{2, 3,...,floor(\sqrt{n})\}$, $m$ does not divide $n \implies n$ is prime

English: If you cannot find a natural divisor > 2 for $n \in \mathbb{N}$ less than (or equal to?) $\sqrt{n}$ then $n$ is prime.

The reason I say "or equal to?" in parentheses, is because I am unsure if that is necessary to translate the logical expression above. But it seems like if it is equal to $\sqrt{n}$ then $\sqrt{n}$ is a divisor, therefore $n$ is not prime. So I think it is safe just to say "less than."

After these line-breaks is the excess information on how I arrived here. I write it all because it helps me practice this kind of math and understand the problems.

I ask this because I am writing a program to check for primes. I got the idea that I do not need to check all the way to $n$ and someone at this website mentioned I need only check to $\sqrt{n}$ and I asked my discrete math instructor, he told me I only need to check to $floor(\sqrt(n))$ which means round down to the greatest integer less than $\sqrt{n}$

So he showed me how to prove:

$\forall n \in \mathbb{N}$, $\forall m \in \{2, 3,...,floor(\sqrt{n})\}$, if $m$ divides $n$ then $n$ is not prime.

The proof is very trivial, and since it still takes me longer than his patience to figure out precisely what the statement says, I later realize this is not what I wanted to prove. I want to prove my statement at the top of the question, that if $\lnot \exists m$ s.t. $m$ divides $n$, then $n$ must be prime.

-

Suppose $n$ is not prime, then $n=rs$ with $r,s>1; r\ge s$

Then $s^2\leq rs=n$.

So if $n$ is not prime it has a factor $s$ with $s\leq \sqrt n$.

And therefore if $n$ has no such factor, it must be prime.

-
So $s^2$ is less than or equal to $rs$ because $s \leq r$ – Leonardo Jan 26 '13 at 9:34
I am still on line 3, all I see is that you took the square root of $s^2 = n$ but I still do not see how $s \leq \sqrt{n} \implies (r \land \lnot r)$ – Leonardo Jan 26 '13 at 9:44
Suppose I have a number $n$ and I want to prove it is prime. I have to show that it it hasn't got a nontrivial factorisation. If it could be factorized, one of the factors would be less than or equal to the square root. So if I show that there is no such factor, I know there is no factorisation at all, and $n$ must be prime. – Mark Bennet Jan 26 '13 at 10:08

If n is not prime, then we only need to prove n is a product of 2 factors, one of them prime-because trial dividing by primes is faster than trial dividing by all the natural numbers- but the other factor can be composite or prime.

-

If you write the natural number $n$ as the product of two natural number $a$ and $b$, then $a$ and $b$ cannot be both $> \sqrt{n}$.

-