A natural number $n$ is prime if and only if, for all primes $p \le \sqrt n$, $p$ does not divide $n$.
I proved the forwards direction, but I'm having trouble proving it backwards
Asked
Active
Viewed 3,920 times
0
Ryan Miller
- 331
- 3
- 12
-
1Try contradiction? ie suppose $n$ is not a prime but the statement holds? – Jack Yoon Feb 07 '17 at 23:12
-
2This is actually false, since you need $n \geq 2$. – Patrick Stevens Feb 07 '17 at 23:15
3 Answers
2
Note that we only consider $n\geq 2$ since $n=1$ satisfies the condition but is not considered prime.
Suppose that for all primes $p\leq \sqrt{n}$ we have $p\not | n$.
Assume now that $n$ is not prime i.e. $n=ab$ with $a,b>1$ integers and wlog $a\leq b$. We will get a contradiction. We have that $a^2 \leq ab=n$ so $a\leq \sqrt{n}$. Since $a> 1$ there exists a prime $p\leq a$ (since $a$ could be a prime) such that $p| a$. Hence there exists a prime $p\leq a\leq \sqrt{n}$ such that $p|n$ which contradicts our initial hypothesis.
Kal S.
- 3,781
-
I am confused. How does your proof show a contradiction? You changed the premise so that $n=ab$ and eventually showed that $p, |, n$, but for a contradiction, did you not need to show that $n=ab$ implies $p\not| n$? – Obsessive Integer Mar 02 '21 at 03:19
2
Prove that, if $n$ is not prime, the smallest non-trivial divisor $m$ of $n$ is necessarily prime and $\le \sqrt n$, by proving that, if it's not prime, it's not the smallest, and likewise if it's $>\sqrt n$.
Bernard
- 175,478
0
If $p$ does not divide $n$ for every prime $p\leq \sqrt n$, then the prime number(s) dividing $n$ must be $>\sqrt n$. If $n$ is not prime then it must be at least divisible by two primes (or twice by one prime).
Join those two facts together.