TITLE: A natural number $n$ is prime if and only if, for all primes $p \le \sqrt n$, $p$ does not divide $n$.
QUESTION [0 upvotes]: 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

REPLY [2 votes]: 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.

REPLY [2 votes]: 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$.
{"set_name": "stack_exchange", "score": 0, "question_id": 2134091}