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. an-1 º 1 (mod n), and
2. am ¹ 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. an-1 º 1 (mod n), and
2. am ¹ 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 = 2m +1 or n = 3*2m +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 aq such that

1. aqn-1 º 1 (mod n), and
2. aq(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 = qmR where q is a prime not dividing R. If there is an integer a such that

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

then each prime factor of n is of the form kqm +1 for some k, that is, n º 1 (mod qm).

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 qm divides e and so qm divides p-1, as required.

When qm 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 = 2mk + 1 where k is odd and assume that 2m > 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 = 2mk with k odd, gcd (2m, k) = 1 and an-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.2m + 1 > 2m for some r. However n = 2mk + 1 < 22m and so Ö n < 2m < 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*2m + 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 x2 - Px + Q. The discriminant D = P2 - 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

Un (P,Q) = a n - b n / a - b

and

Vn (P,Q) = a n + b n

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

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

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

Lemma 4.6.

1. Vn2 - DUn2 = 4Qn
2. Un2 - Un- 1Un+1 = Qn-1
3. DUn = Vn+1 - QVn-1
4. Vn = Un+1 - QUn-1
5. Um+n = UmUn - QnUm-n
6. Vm+n = VmVn - QnVm-n = DUmUn + QnVm-n
7. 2Um+n = UmVn + UnVm
8. 2QnUm-n = UmVn - UnVm
9. Um+n = UmUn+1 - QUm-1Un
10. 2Vm+n = VmVn + DUmUn
11. U2n = UnVn
12. V2n = Vn2 - 2Qn

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

Lemma 4.7

1. Un º Vn-1 (mod Q)
2. Vn º Pn (mod Q)
3. If p is an odd prime, then Ukp º D(p-1)/2Uk (mod p)
4. If p is an odd prime, then Upe º D((p-1)/2)e (mod p) - in particular , Up º (D/p) (mod p)
5. If p is an odd prime, then Vp º P (mod p)
6. If n, k ³ 1, then Un divides Ukn
7. If n, k ³ 1 and k is odd, then Vn divides Vkn

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|pi) 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 (a2n|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 x2 º n (mod P) has a solution, then (n|pi) = 1 for each pi and hence (n|P) = 1, however the converse is not true, since an even number of (n|pi) = -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 = P2 - 4Q, where gcd(P,Q) = 1 or gcd(n,Q) = 1 and such that n divides Un+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 = P2 - 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 = P2 - 4Q, where gcd(P, Q) = 1 or gcd(N, Q) = 1 and such that n divides Un+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.