If a number cannot be...

Question

If there exists such a number which cannot be divided by some other number, which is equivalent to, or smaller than the square root of itself, it is a prime number.

This is a rather trivial theorem but I would like to see different takes on proving this.

Answer 1

Suppose that $n$ is a positive integer such that for all $1<m\leq\sqrt{n}$, $m$ does not divide $n$. Suppose, to the contrary, that $n$ is not prime. Then there exist positive integers $a$ and $b$ greater than $1$ such that $ab=n$. Without loss of generality, suppose that $a$ is the smaller of the two. We know by hypothesis that $a>\sqrt{n}$, so $ab\geq a^2>n$. This is a contradiction, so $n$ must be prime.

Answer 2

if $n$ is compound then $n=rs$ with $\min(r,s) \gt 1$

suppose $r \gt \sqrt{n}$ and $s \gt \sqrt{n}$

then $n = rs \gt \sqrt{n}\sqrt{n}=n$ a contradiction.

so if $n$ is compound we must have $\min(r,s) \le \sqrt{n}$