To find whether $a$ is a prime number

Question

I have been using this rule to determine whether a number is a prime number, but not how to prove it. Why it has to be $\sqrt{a}$?

If $a$ is not divisible by all the prime numbers less than or equal to $\sqrt{a}$, then $a$ is a prime number.

Answer 1

Assume $a$ is not a prime number. Then it can be written as $a = bc$ with $b, c \ge 2$. Then the smaller of $b, c$ is less than or equal to $\sqrt a$, for otherwise the product would be greater than $\sqrt a \, \sqrt a = a$. This smaller factor is then either a prime itself or has a prime factor that is even smaller.

Answer 2

Divisors come in pairs. If $n$ divides $a$, so does $a/n$, as $\sqrt{a}\sqrt{a}=a$, one of the factors in a pair must be smaller than or equal to $\sqrt{a}$.

Answer 3

Just another point of view

Suppose that $a$ is divisible by a prime $p$. This means that: $$a = p \cdot k \Rightarrow p = \frac{a}{k}.$$ Moreover, suppose that $p > \sqrt{a}$, then:

$$\frac{a}{k} > \sqrt{a} \Rightarrow k < \sqrt{a}.$$

This means that I can only use the primes $p \in [\sqrt{a}, a]$ to determine if $a$ is prime, instead of the set $[0, \sqrt{a}]$.

Which is the set that best suits for the algorithm?

I guess the smallest, since you will have a smaller number of primes to be tested. The set $[\sqrt{a}, a]$ has length $a-\sqrt{a}$, while the set $[0, \sqrt{a}]$ has length $\sqrt{a}$.

Notice that: $$\sqrt{a} < a-\sqrt{a} \Rightarrow 2\sqrt{a} < a \Rightarrow \sqrt{a} > 2 \Rightarrow a > 4.$$

In general, you want test a number $a$ bigger than $4$. For this reason, you just look to the set $[0, \sqrt{a}]$... it is just faster!

---

Example.

Take $a = 77$ and notice that $\sqrt{a} \simeq 8.78$. If you use the set $[0, \sqrt{a}]$, the you will have to check if $a$ is divisible by $3,5,7$ (only three numbers). On the other hand, if you choose the set $[\sqrt{a}, a]$, you will have to check if $a$ is divisible by $11, 13, 17, 19, 23, 29, 31, 37, ...$. Hey, this is too much, no?!

Answer 4

Let $ab=p$ where $a,b$ are possible factors of prime candidate $p$.

If you find a factor $b \geq \sqrt{p}$, then $a \leq \sqrt{p}$.

But if you checked all $a \leq \sqrt{p}$ and didn't find any factors ...

Answer 5

For every prime divisor of $n$ that is less than $n$ and greater than $\sqrt{n}$, there must be a prime number less than $\sqrt{n}$ that divides $n$.

This follows from the fact that it is impossible for a number $n$ to have two prime divisors $p$ and $q$ that were both greater than $\sqrt{n}$, since then their product would be $$pq>(\sqrt{n})^2=n$$

Thus we need only check the primes in the range $1,...,\sqrt{n}$ to see if they divide $n$.

Answer 6

This may be easiest to see if illustrated by example.

Consider the factors of $16$ as found by trial division.

That is, we will divide $16$ by $1$ then $2$ then... and each time the remainder is $0$ we will record both the divisor and the quotient as a factor pair:

$1$: Yes, this yields the factor pair $(1, 16)$.

$2$: Yes, this yields the factor pair $(2, 8)$.

$3$: No, $16/3$ is not a whole number, i.e., it has remainder $1$.

$4$: Yes, this yields the factor pair $(4,4)$.

$5$: No, $16/5$ is not a whole number, i.e., it has remainder $1$.

$6$: No, $16/6$ is not a whole number, i.e., it has remainder $4$.

$7$: No, $16/7$ is not a whole number, i.e., it has remainder $2$.

$8$: Yes, this yields the factor pair $(8,2)$.

$\ldots$

Note that we already had that last factor pair, though in the other order, as $(2,8)$.

Trying other examples and searching for factor pairs, you will always find that, at some point, they repeat. (If the number is prime, e.g., $11$, then the only factor pairs will be $(1, 11)$ and $(11, 1)$.)

The question now becomes, at what point do the numbers repeat? That is, when can we stop carrying out our trial division?

For the case of $16$ they repeat after $\sqrt{16} = 4$.

More generally, all the factors appear in this way once you check up to the square root.

For if the target number is $N$ and you've found all factors less than or equal to $\sqrt{N}$, could there be new factors? If so, you'd need to find a factor pair with two new factors, i.e., each of which is greater than $\sqrt{N}$.

But then their product would be greater than $\sqrt{N}\sqrt{N} = N$; so, they cannot form a factor pair: Their product is bigger than the target number!