Prime and Unique Factorization Proof

Question

I could use some help with this question here:

Let $n ∈ Z, n > 1$. Prove that if n is not divisible by any prime number less than or equal to $√n$, then n is a prime number.

Here I assumed that n is divisible by some result less than √n so this means that there exists an x ∈ Z which is unique and prime. This means a set S = {$x ∈ Z$ | n is equal to or less than $√n_1$, $√n_2$...$√n_k$}. I feel like I'm going in the wrong direction with this proof, can any help point me in the right direction if I am doing this wrong? Thanks!

Answer 1

Let's prove the contrapositive:

If $n$ is not a prime number, then $n$ is divisible by a prime number less than or equal to $\sqrt n$.

If $n$ is not a prime number. then $n=ab$ with $a,b > 1$.

If $a > \sqrt n$ and $b > \sqrt n$, then $ab > n$.

So, at least one of $a$ or $b$ is at most $\sqrt n$. Wlog, let's say it's $a$.

Then, since $a>1$, take any prime divisor of $a$. Then $p$ also divides $n$ and $p \le a \le \sqrt n$.