0

For this problem, you are provided with the following definition:

"A Test for Primality is the following: Given an integer n > 1, to test whether n is prime check to see if it is divisible by a prime number less than or equal to its square root. If it is not divisible by any of these numbers then it is prime."

I am asked to prove this.

enter image description here

I tried to prove it directly as such:

enter image description here

I'd appreciate any feedback.

Henry
  • 157,058

2 Answers2

0

Let $2<n=ab$ is composed with $2\le a\le b<n$. Then $a \le\sqrt{n}$ (why?). Hence so is any prime factor of $a$.

szw1710
  • 8,102
  • What if I said, suppose to the contrary that a > root of n but then a^2 > ab and a > b which gives us a contradiction that a can be less than or equal to b? –  Nov 29 '19 at 01:12
0

If $n$ is prime than there is no natural number other than $1$ and $n$ that divides $n$.

So if $n$ is not prime then there is at least one natural number other than $1$ and $n$ that divides $n$. Call one of these numbers $k$.

There are 3 possibilities.

  1. $k > n$.

Strike this out. If $k > n>0$ then $1 > \frac nk > 0$ and $\frac nk$ is not an integer and $k\not \mid n$. So this is impossible.

  1. $n > k > \sqrt n > 0$. If $k|n$ then $\frac nk = m$ is an integer and as $k > \sqrt n$ then $m =\frac nk < \frac n{\sqrt n} = \sqrt n$.

Now $\frac nm = k$ is an integer so $m|n$. And $m < \sqrt n$. So there is a natural number $m\le \sqrt n$ that divides $n$!

  1. $1 < k \le \sqrt n$. Then there is a natural number $k \le \sqrt n$ that divides $n$.

....

So..... If $n$ is not prime then there will be a natural number between $1$ (not inclusive) and $\sqrt n$ (inclusive possibly) that divides $n$.

fleablood
  • 124,253
  • Just a quibble, but since you add the parenthetical phrase "inclusive possibly", it would be better to revise the preceding phrase to "between 2 and $\sqrt n$". That is, possibly $\sqrt n$ turns out to be an exact integer (and prime), and the claim can only be satisfied by $\sqrt n$ being a prime divisor of $n$. But the other endpoint $1$ always divides $n$ (but is not related to $n$ not being a prime). – hardmath Dec 03 '22 at 22:26