Primality Testing

Prime numbers constitute one of the most vexing sets in mathematics. With most sets we have an algorithm or formula that lets us generate all of the elements of the set and only the elements of the set. We have a straightforward way to produce the n-th element of the set. We don’t have such a way for the prime numbers. No one has yet discovered an algorithm or formula that will enable anyone to generate all of the prime numbers and only the prime numbers. Until such an algorithm or formula comes to light, the only way in which we can find prime numbers is by guessing and testing.

Suppose that we suspect a number N of being prime. To prove that suspicion, we divide N, one at a time, by each of the prime numbers less than N/2. We don’t need to divide by any of the composite numbers, because they include the primes as factors: the divisions would simply be redundant. And we don’t need to divide by any primes between N/2 and N, because the quotient would lie between one and two, so it could not possibly be an integer. That procedure is reasonable for relatively small values of N, but if N has hundreds of digits or more, that procedure would overwhelm a computer. We need something more efficient.

Two procedures, taken together, will provide an efficient way of testing large numbers for primality. We start with the rule of six and then apply the powers-of-two theorem.

If we divide N by six, we will get a quotient M and a remainder of 1, 2, 3, 4, or 5. We can see readily that 6M+2, 6M+3, and 6M+4 are all evenly divisible by two or three; therefore, they are composite and can be dismissed from our consideration. Numbers of the form N=6M+1 or N=6M+5 may be prime, but we still have to test them. This part of the process eliminates two thirds of the number line from consideration.

Next we exploit a strange property of the binomial
theorem. That theorem tells us how to calculate the coefficients of the
polynomial (x+y)^{n}. Those coefficients are the elements of the set of
the partial products of (1+1)^{n}. For example, if n=6, we have the set
{1, 6, 15, 20, 15, 6, 1}. In general we can calculate the p-th element of the n-th
set through the equation

(Eq’n 1)

in which p takes values between zero and n (and we note that 0!=1).

Those coefficients are all integers, so we know that n! must be evenly divisible by (n-p)! and p! together. The division by (n-p)! removes the first n-p factors from n! and the division by p! removes the first p integers of the number line from the factors n-p to n. So for n=6 and p=3 we have

(Eq’n 2)

That second division separates the composite numbers from the prime numbers.

If n is a composite number with a factor q, then when p=q that factor is removed from the numerator and there is none to replace it. Thus, in that case, the coefficient that we calculate is not evenly divisible by n. But if n is a prime number, there is no factor q to be removed and every coefficient in the set is evenly divisible by n. So if n is composite, at least one coefficient is not evenly divisible by n and the sum of all the coefficients, excluding the first and last, is also not evenly divisible by n. But if n is prime, the sum of all the coefficients in the n-th set of binomial coefficients, excluding the first and last, is evenly divisible by n.

The sum of all of the terms in the n-th binomial expansion
is 2^{n}. That sum minus the first and last terms is evenly divisible by
n if and only if n is a prime number. So to test our number N for primality we
divide 2^{N}-2 by N and if the result is an integer, N is prime. A
digital computer can do that easily.

habg