Proof hint, prime numbers

Question

I am trying to prove this:

Prove that a positive integer $n$ is a prime number, if no prime $p$ less than or equal to $\sqrt n$ divides $n$.

This is how I thought of starting:

Let us assume the smallest prime factor of $n$ to be $P$. So, $n = (m)(P)$ From this it follows that $(n) \geq (P)^2$ or $\sqrt n \geq (P)$ i.e $n$ has at least one prime divisor smaller than $\sqrt n$ whenever it is composite. So if it has no prime divisor, then it must be prime.

However, I'm not quite satisfied with the proof. Can someone please provide me an easier approach to the proof?

Answer 1

Let $n$ be an integer such that no prime number, less than or equal to $\sqrt{n}$, divides $n$.

Consider a prime divider $q$ of $n$. By assumption, $q > \sqrt{n}$. So $\frac{n}{q} < \sqrt{n}$. But all the dividers of $\frac{n}{q}$ are also dividers of $n$, so by assumption, these dividers are all not prime. This means that $\frac{n}{q}$ has no prime divider, so the only possibility is that $\frac{n}{q} = 1$.

So we proved that the only prime divider of $n$ is $n$, in other words, $n$ is prime.

Answer 2

Hint:

You can base your proof on this lemma:

Lemma: If a positive integer $n$ is composite, it has a non-trivial divisor $d\le\sqrt n$.

Indeed, let $m$ be a non-trivial divisor of $n$. Then, either $m\le\sqrt n$, and you can take $d=m$, or $m>\sqrt n$. In the latter case, it's easy to check that $1< m'=n/m<\sqrt n$, and you can take $d=m'$.

Answer 3

Let $n \in \mathbb{Z}^{+}$ such that $\not\exists \ p \le \sqrt{n},\ p |n$ provided $p \in P$. Then, we have to prove that $n$ is prime. Let us suppose to the contrary that $n$ is not a prime integer. We may write $$n=ab, \ 1\lt a\le b \implies a\le \sqrt{n}, \ b \ge \sqrt{n}$$ Let $p$ be a prime factor of $a$. Then $p \le a \le \sqrt{n}, \ p|a$. $$p|a \implies p|ab \iff p|n$$ This contradicts our assumption. Hence we must've had made a wrong assumption to start with. QED