# To find whether $a$ is a prime number

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.

• HInt $\$ The least nontrivial factor of a composite number is less than its square-root. – Gone May 28 '16 at 2:14

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.

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

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?!

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

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

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!