2

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?

Bob Happ
  • 582
user648652
  • 43

3 Answers3

2

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.

TheSilverDoe
  • 29,720
2

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

Paras Khosla
  • 6,481
  • I'd appreciate if you use the symbols in words. – user648652 Feb 27 '19 at 15:29
  • "$n\in \mathbb{Z}^{+}$" means $n$ is a positive integer. "$\not \exists \ p, \ p|n$" means there does not exist any $p$ such that $p$ divides $n$. $P$ is used to denote the set of prime numbers. "$\implies$" means implies and "$\iff$" means if and only if. – Paras Khosla Feb 27 '19 at 15:31
  • I don't get the proof. Can you simplify it more – user648652 Feb 27 '19 at 15:33
  • We just suppose that the proposition is not true. Then we prove by contradiction. Notice if a number is not prime it is expressible as a product of two distinct integers which is why we can write $n=ab$. Also if $p$ is a factor of $a$, then $p \le a$ and if an integer divides the other it also divides that integer times any other non-zero integer which is the rationale behind the statement "$p|a \implies p|ab$" and recall $ab$ is? – Paras Khosla Feb 27 '19 at 15:36
  • This is exactly the argument in the linked dupe. – Randall Feb 27 '19 at 16:16
  • @Randall I did not visit the link earlier. I came up with it myself. – Paras Khosla Feb 27 '19 at 17:15
0

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'$.

J. W. Tanner
  • 60,406
Bernard
  • 175,478