Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
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
1  
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
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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