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

- a
^{n}^{-1}º 1 (mod n), and - 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

- a
^{n}^{-1}º 1 (mod n), and - 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

- a
_{q}^{n}^{-1}º 1 (mod n), and - 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^{m}R where q is a prime not
dividing R. If there is an integer a such that

- a
^{n}^{-1}º 1 (mod n), and - 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^{m}k
+ 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^{m}k 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^{m}k + 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^{2}
- Px + Q. The discriminant D = P^{2}
- 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 ^{n} - b ^{n}
/ a -
b

and

V_{n}^{
}(P,Q) = a ^{n} + b ^{n}

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.

- V
_{n}^{2}- DU_{n}^{2}= 4Q^{n} - U
_{n}^{2}- U_{n}_{- 1}U_{n+1}= Q^{n}^{-1} - DU
_{n}= V_{n+1}- QV_{n}_{-1} - V
_{n}= U_{n+1}- QU_{n}_{-1} - U
_{m+n}= U_{m}U_{n}- Q^{n}U_{m}_{-n} - V
_{m+n}= V_{m}V_{n}- Q^{n}V_{m}_{-n}= DU_{m}U_{n}+ Q^{n}V_{m}_{-n} - 2U
_{m+n}= U_{m}V_{n}+ U_{n}V_{m} - 2Q
^{n}U_{m}_{-n}= U_{m}V_{n}- U_{n}V_{m} - U
_{m+n}= U_{m}U_{n+1}- QU_{m}_{-1}U_{n} - 2V
_{m+n}= V_{m}V_{n}+ DU_{m}U_{n} - U
_{2n}= U_{n}V_{n} - V
_{2n}= V_{n}^{2}- 2Q^{n}

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

Lemma 4.7

- U
_{n}º V_{n}_{-1}(mod Q) - V
_{n}º P^{n}(mod Q) - If
p is an odd prime, then U
_{kp}º D^{(p}^{-1)/2}U_{k}(mod p) - If
p is an odd prime, then U
_{p}e º D^{((p}^{-1)/2)e}(mod p) - in particular , U_{p}º (D/p) (mod p) - If
p is an odd prime, then V
_{p}º P (mod p) - If
n, k ³ 1, then U
_{n}divides U_{kn} - 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.

- (m|P)(n|P) = (mn|P)
- (n|P)(n|Q) = (n|PQ)
- if m º n (mod P) then (m|P) = (n|P)
- if
gcd(a, P) = 1 then (a
^{2}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^{2} º 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^{2} - 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^{2} -
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^{2} - 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.