Section 4 - Primality Proofs

Let us now try to develop a number of more useful practical proofs of primality. The first result is the nearest we can get to a direct converse of Fermat's Little Theorem.

Lemma 4.1 (Lucas). Let n > 1. If there exists an integer a > 1 such that

1. a^n-1 º 1 (mod n), and
2. a^m ¹ 1 (mod n) for m < n-1,

then n is prime.

Proof : By Lemma 2.5, all we need to do is show that j(n) = n-1. It is sufficient to show that there exists an integer a of order n-1 modulo n (since we know that j(n) < n-1 for any composite n). This is exactly our supposition.

This result is hardly of use as it requires n-2 multiplications by a and remainders modulo n. However, we can obtain a more useful result without too much effort.

Lemma 4.2 (Lucas). Let n > 1. If there exists an integer a > 1 such that

1. a^n-1 º 1 (mod n), and
2. a^m ¹ 1 (mod n) for m < n such that m | n-1

then n is prime.

Proof : In a nice twist, the proof of this is exactly the same as the proof for Lemma 4.1, since we know that the order of a must divide j(n) = n-1 by Lemma 2.13.

This result is effective when the number of factors of n-1 is small, e.g. n = 2^m +1 or n = 3*2^m +1 or n-1 = NP where N is a product of several small primes and P is a single large prime (but not as large as n). However, it requires a single value of a for all factors, and as the number of factors rises, it becomes more time-consuming to find it. This is overcome by the next result, a direct improvement of the previous one.

Lemma 4.3 (Brillhart-Lehmer-Selfridge). Let n > 1. If, for every prime factor q of n-1, we can find an integer a_q such that

1. a_q^n-1 º 1 (mod n), and
2. a_q^(n-1)/q ¹ 1 (mod n)

then n is prime.

Proof : Again, it is enough to show that j(n) = n-1. If this is false, then there is a prime q such that q divides n-1 but doesn't divide j(n). Let e be the order of a modulo n. Then e divides n-1 by (i) and e doesn't divide (n-1)/q by (ii). Hence q divides e. Now, since e divides j(n) by Lemma 2.13, we have that q divides j(n), a contradiction. Hence result.

We now consider partial rather than full factorisations of n-1 in the following :

Lemma 4.4 (Pocklington). Let n-1 = q^mR where q is a prime not dividing R. If there is an integer a such that

1. a^n-1 º 1 (mod n), and
2. gcd (a^(n-1)/q -1, n) = 1,

then each prime factor of n is of the form kq^m +1 for some k, that is, n º 1 (mod q^m).

Proof : Let p be a prime factor of N such that p ¹ q. Let e be the order of a modulo p, so that e divides p-1. If e divides (n-1)/q, then a^(n-1)/q º 1 (mod p), contrary to (ii), since p divides n. Hence e does not divide (n-1)/q, and so q does not divide (n-1)/e. Hence q^m divides e and so q^m divides p-1, as required.

When q^m is large, this result substantially restricts the form of divisors of n, and in certain cases, such as the following, allows us to develop explicit tests for primality.

Lemma 4.5 (Proth-Pocklington). Let n = 2^mk + 1 where k is odd and assume that 2^m > k. If there exists and integer a such that a^(n-1)/2 º -1 (mod n), then n is prime.

Proof : We have n-1 = 2^mk with k odd, gcd (2^m, k) = 1 and a^n-1 º 1 (mod n). Since n is odd, we have gcd (a^(n-1)/2 -1, n) = 1. Hence by Lemma 4.4, each prime factor p of n is of the form p = r.2^m + 1 > 2^m for some r. However n = 2^mk + 1 < 2^2m and so Ö n < 2^m < p. Hence n is prime.

This is the standard result that is used by Yves Gallot in his proth.exe primality testing program. Since the result is comparatively easy to implement on a computer, numbers of the form k*2^m + 1 are regularly amongst the largest primes known. Apart from this, there are several other important reasons for considering numbers of this form, as will be seen.

Pocklington improved Lemma 4.4 to the case where the factored part of n-1 involves more than just a prime power. Later, Brillhart, Lehmer and Selfridge expanded the above ideas further, producing a number of variants to deal with integers of other simple forms.

For completeness, a number of similar results exist for the case when n+1 can be reduced to a simple form. For this we need an entirely new concept.

Definition. Consider the polynomial x² - Px + Q. The discriminant D = P² - 4Q and the roots are a and b are (P ± Ö D)/2, so that a + b = P, a * b = Q and a - b = Ö D. We choose P and Q so that D ¹ 0. The sequences

U_n (P,Q) = a ⁿ - b ⁿ / a - b

and

V_n (P,Q) = a ⁿ + b ⁿ

are known as the Lucas sequences for P and Q. The V_n are sometimes known as the companion Lucas sequences to the U_n. These definitions ensure irrational roots always cancel, so that U_n and V_n are at the very least rational numbers, and often integers.

The Fibonacci numbers are the Lucas sequence U_n (1,-1), and their companions V_n (1,-1) are the Lucas numbers.

There are literally hundreds of simple formulae involving Lucas sequences. Here are a few :

Lemma 4.6.

1. V_n² - DU_n² = 4Qⁿ
2. U_n² - U_{n- 1}U_n+1 = Q^n-1
3. DU_n = V_n+1 - QV_n-1
4. V_n = U_n+1 - QU_n-1
5. U_m+n = U_mU_n - QⁿU_m-n
6. V_m+n = V_mV_n - QⁿV_m-n = DU_mU_n + QⁿV_m-n
7. 2U_m+n = U_mV_n + U_nV_m
8. 2QⁿU_m-n = U_mV_n - U_nV_m
9. U_m+n = U_mU_n+1 - QU_m-1U_n
10. 2V_m+n = V_mV_n + DU_mU_n
11. U_2n = U_nV_n
12. V_2n = V_n² - 2Qⁿ

These can all be proved by simple manipulation of the defining equations. More useful directly to us are the following :

Lemma 4.7

1. U_n º V_n-1 (mod Q)
2. V_n º Pⁿ (mod Q)
3. If p is an odd prime, then U_kp º D^(p-1)/2U_k (mod p)
4. If p is an odd prime, then U_pe º D^((p-1)/2)e (mod p) - in particular , U_p º (D/p) (mod p)
5. If p is an odd prime, then V_p º P (mod p)
6. If n, k ³ 1, then U_n divides U_kn
7. If n, k ³ 1 and k is odd, then V_n divides V_kn

From these and more advanced results, primality tests analogous to those for n-1 above can be obtained for n+1. Full proofs of these would take up too much effort on my part to type in, so I will simply quote them. However, for this I'll need the following definition.

Definition : Let P = and n be a positive integer. Then the Jacobi symbol (n|P) is defined as follows :

(n|P) =

where (n|p_i) is the Legendre symbol.

The Jacobi symbol is a logical extension of the Legendre symbol and behaves much in the same way, e.g.

1. (m|P)(n|P) = (mn|P)
2. (n|P)(n|Q) = (n|PQ)
3. if m º n (mod P) then (m|P) = (n|P)
4. if gcd(a, P) = 1 then (a²n|P) = (n|P)

The results in Lemmas 3.3, 3.4 and 3.7 have direct analogues. However, there is one important distinction: if the congruence x² º n (mod P) has a solution, then (n|p_i) = 1 for each p_i and hence (n|P) = 1, however the converse is not true, since an even number of (n|p_i) = -1 cancel each other out but ensure that the congruence cannot have a solution.

We can now state our n+1 primality tests.

Lemma 4.8. Let n > 1, n odd, and assume that we can find D such that (D/n) = -1. If for every prime factor q of n+1, we can find a Lucas sequence U with discriminant D = P² - 4Q, where gcd(P,Q) = 1 or gcd(n,Q) = 1 and such that n divides U_n+1 but n does not divide U_(n+1)/q, then n is prime.

There is an analogous result for companion Lucas sequences which is slightly better.

Lemma 4.9. Let n > 1, n odd, and assume that we can find D such that (D/n) = -1. If for every prime factor q of n+1, we can find a companion Lucas sequence V with discriminant D = P² - 4Q, where gcd(P,Q) = 1 or gcd(n,Q) = 1 and such that n divides V_(n+1)/2 but n does not divide V_(n+1)/2q, then n is prime.

The next result is the analogue of Pocklington's test, this time for partial factorisation of n+1.

Lemma 4.10 (Morrison). Let n > 1, n odd, n = FR where gcd(F, R) = 1 and F is fully factored. Again, assume that we can find D such that (D/n) = -1. If for every prime factor q of F, we can find a Lucas sequence U with discriminant D = P² - 4Q, where gcd(P, Q) = 1 or gcd(N, Q) = 1 and such that n divides U_n+1 but gcd(U_(n+1)/q, N) = 1, then each prime factor p of N is of the form p º (D/p) (mod F). Additionally, if F > Ö n +1 then n is prime.

It is important to note that calculating Lucas sequences to high indices is relatively easy, given the relationships listed in Lemma 4.6.

Armed with these primality tests, in Section 5 we can now proceed to search for primes of specific forms.