Primality test; Wilson's Theorem

Fermat’s little theorem may be used as a primality test, to verify that a number is not prime. We have seen that if p is a prime number whatever a we have

Then we can state the following proposition

Proposition 4.10.1. If there exists a number a such that

then n is not prime.

For instance, n = 6 is not prime because 2⁶ ≢ 2 (mod 6).

Proposition 4.10.2. (Wilson's Theorem) If p is prime, then

Proof. For p = 2 and p = 3 the theorem is obvious. So, assume p > 3. Consider the congruence

where a is one of the integers 1 ≤ a ≤ p − 1. As GCD(a, p) = 1, this congruence admits exactly one solution a' modulo p, with 1 ≤ a' < p. Can be a equal to a' and if so when? The congruence

means that a² − 1 has p has a factor. Therefore, since

Either p divides a + 1 or p divides a − 1. It follows that either a − 1 ≡ 0 (mod p), that is, a = 1, or a + 1 ≡ 0, that is, a = p − 1.

The other solutions with a ≠ a' are, leaving out the two previous one, are the elements 2, 3, ..., p − 2 and can be paired up into (p − 3)/2 pairs {a, a'}, such that

By multiplying together all the congruences, we obtain 2 · 3 · ··· · (p − 2) = (p − 2)! ≡ 1 (mod p). Now, by multiplying both sides by p − 1 ≡ −1 (mod p), we find that (p − 1)! ≡ p − 1 (mod p), which is our claim.□

The inverse of this theorem is also true:

Proposition 4.10.3. If (n − 1)! ≡ −1 (mod n), then n is prime.

Proof. If n were not a prime, it would have a divisor b, with 1 < b < n, which, being a divisor of n, would divide (n − 1)! + 1 as well. But b should appear among the factors of (n − 1)!, as 1 < b < n, so b | (n − 1)!. These two relations imply that b divides 1, which is a contradiction.□

Similarly to Fermat’s little theorem, Wilson’s theorem provides a primality test. In principle, the test works as follows: given n, compute (n − 1)! + 1 and verify whether it is divisible by n or not. If it is not, and only in this case, n is prime.

However such a test is unfeasible in practive, (n − 1)! is exponential and we do not an algorithm for its rapid calculation.

The algorithms used to check whether a given number is prime or not are know as primality tests. The most natural, but by far not the most efficient way to determine whether a number n is prime consists in verifying that it is not divisible by any number preceding it, that is to say, by 2, 3, 4, . . ., n − 1.
A better approach is Eratosthenes's sieve a useful procedure handed down from antiquity able to reduce unnecessary trial divisions; Eratosthenes (276–194 BC) from Cyrene (in what is now Lybia) was a contemporary of Archimedes, and the head librarian of the great library of Alexandria. One of his most impressive accomplischments was to accurately calculate the circumference of the earth using only geometry. This primality test is based on the Fundamental Theorem of Arithmetic, which assures us that every positive integer can be written in a unique way as a product of prime numbers, though it does not provide any algorithm to find the factorisation of a given number. The sieve of Eratosthenes allows in principle, to determine all prime numbers smaller than or equal to a fixed positive integer number n.

Proposition 4.10.4. (Eratosthenes's sieve) If a positive integer n is not divisible by any prime number smaller than or equal to √n, then n is prime.

Proof. Assume n to be reducible, that is to say that n = ab with a and b integers such that 1 < a < n and 1 < b < n. One of the factors, a or b, is necessarily smaller than or equal to √n: otherwise we would have n = ab > √n · √n = n, which is impossible. So n has a factor, say b, smaller than or equal to n. If it is prime, the proposition is proved. Otherwise, b has a prime factor p, and p < b ≤ √n. □

So the method consists of the following steps:

1. Write a list of all natural numbers from 2 to the given number n.

2. Delete from this list all multiples of two (4, 6, 8, etc.), since these are not prime.

3. Delete from this list all remaining multiples of three (9, 15, etc.), since these are not prime.

4. Find in the list the next remaining prime number (5) and if 5 ≤ √n delete all numbers that are multiples of 5, and so on.

5. stop this process as soon as you reach the last prime p ≤ √n and cross off its multiples. All the non-crossed off numbers are prime.

For example, we can find all primes less than 24 by just crossing off all multiples of 2 and 3, since 5 > √24:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Example 4.10.5. To prove that the number 173 is prime, it is sufficient to prove that it is not divisible by any prime smaller than or equal to √173, that is to say that it is not divisible by 2, 3, 5, 7, 11, 13. The reader may easily check that this is the case.

We can use the sieve of Eratosthenes as a factorization method. To factorize an integer n we check whether it is divisible by all primes 2, 3, ... , √n not underlined.

1. if n is not divisible by any of these numbers, then n is a prime number;

2. Otherwise, denoting by n₁ a factor of n, apply the same procedure to n₁ and n/n₁ (which is an integer), arriving finally to the complete factorisation of n in prime factors.

In order to use the sieve of Eratosthenes, however, we need to know the prime numbers smaller than or equal to √n, and this may result incovinient, there are no known recurrence formulas to compute prime numbers, and so there is no efficient method to generate prime numbers. So we may use the method in a weaker form, and check if n is divisible by 2, 3, 4, 5, ..., [√n], that is, by all integer numbers smaller than or equal to n. By the way, this is not an efficient method, as its complexity is exponential.

Fermat's Factorization Method

To factorize an integer n in many cases it is more efficient the following method due to Pierre de Fermat. It is based of the following points:

1. We can suppose n to be odd. (If n were even we could repeatdlty divide by 2 until an odd integer resulted).

2. when n is odd, factoring n is equivalent to determining two integers x and y such that:

   n = x² − y², x,y ∈ ℕ

   Indeed if n = x² − y², then n = (x + y) (x − y) is a factorization of n. Conversely for a given odd positive integer n > 1, if n = a ⋅ b, with a ≥ b ≥ 1, then

   $$n={\left(\frac{a+b}{2}\right)}^2-{\left(\frac{a-b}{2}\right)}^2$$

   where (a + b)/2, (a − b)/2 ∈ ℕ since n is odd both a and b are odd and a ± b is even.

3. Determining x and y such that n = x² − y² is equivalent to determinining x such that x² − n is a square (=y²).

Fermat factorisation method works as follows: first of all determine the smallest positive integer k such that k² ≥ n; then successively compute the differences

k² − n,   (k + 1)² − n,   (k + 2)² − n, ...

until a value s ≥ k is found such that t² − n is a square. Notice that this process terminates at most when s = (n + 1)/2, as

$${\left(\frac{n+1}{2}\right)}^2-n={\left(\frac{n-1}{2}\right)}^2$$

a value that can be obtained only when the number n is prime, so that the factorization of n is trivial

$$n=(\frac{n+1}{2}+\frac{n-1}{2})\cdot (\frac{n+1}{2}-\frac{n-1}{2})=n\cdot 1$$

Example 4.10.6. Use Fermat's method to factor 8777.

Solution. We see that 93² < 8777 < 94². Therefore we have to consider the values of k² − 8777 for k ≥ 230. Taking k = 94, 95 , .. we have

94² − 8777 = 8836 − 8777 = 59  not a square
95² − 8777 = 9025 − 8777 = 248  not a square
96² − 8777 = 9216 − 8777 = 439  not a square
97² − 8777 = 9409 − 8777 = 632  not a square
98² − 8777 = 9604 − 8777 = 827  not a square
99² − 8777 = 9801 − 8777 = 1024  a square!

So x = 99 and y = 32 which yields

8777 = (99 + 32) ⋅ (99 − 32) = 131 ⋅ 67 ■

Fermat numbers

The mathematician P. de Fermat considered the question of which odd prime numbers can be written in the form p = 2^k + 1, where k is a positive integer. Fermat showed that for 2^k + 1 to be prime, k must be a power of 2, i.e. k = 2ⁿ or equivalently k has no odd factors, for suppose it had an odd factor t = 2h + 1, we would have

2^k + 1 = 2^tr + 1 = (2^r)^t + 1
= (2^r + 1) ((2^r)^2h − (2^r)^{2h −1} + ... + (2^r)² − 2^r + 1)

where we have employed an algebraic identity known as "difference of Powers Formula". Thus if we want a number in the form 2^k + 1 to be prime the exponent k must have the form 2²ⁿ.

Definition 4.10.7. A Fermat number is an integer of the form

N_n = 2²ⁿ + 1 □

The first Fermat numbers are

N₀ = 3,   N₁ = 5,  N₂ = 17,   N₃ = 257,  N₄ = 65537

Fermat conjectured that all Fermat numbers were prime. However in 1732, Leonhard Euler showed that N₅ is not a prime, showing its factorization

N₅ = 4294967297 = 641 ⋅ 6700417

Until today no further Fermat number has been found to be prime. The greatest known Fermat number not prime is N₂₃₄₇₁.

Fermat prime numbers are involved as we shall see in next chapters in the constructibility with the ruler and compass of regular n-polygons.

« Euler's function and theorem Index Cryptology »