11
$\begingroup$

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.

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

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.

| cite | improve this answer | |
$\endgroup$
10
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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!

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.