
Have you ever looked at the list of largest known primes? The most obvious feature of the largest few thousand primes p is that in almost every case either p1 or p+1 is trivially factored. Why is that? Because these are the numbers easiest to prove prime! In this section we will show how we can use Fermat like tests for n if we know enough factors of n1. These are tests that prove primality, they do not just suggest that primality is (however highly) probably.
In 1891 Lucas turned Fermat's Little Theorem into a practical primality test. Here is Lucas' test as strengthened by Kraitchik and Lehmer (see [BLS75]):
Theorem 1: Let n > 1. If for every prime factor q of n1 there is an integer a such thatthen n is prime.
 a^{n}^{1} ≡ 1 (mod n), and
 a^{(n1)/q} is not 1 (mod n);
We will prove this theorem because we have a great deal to learn from it. (If you lose your way here, then just move on to the next theoremsince in this case you must be taking me at my word anyway.)
Proof: To show n is prime we need only show phi(n) = n1 (here phi(n) is Euler totient function), or more simply, that n1 divides phi(n). Suppose this is not the case, then there is a prime q and exponent r>0 such that q^{r} divides n1, but not phi(n). For this prime q we must have an integer a that satisfies the conditions above. Now let m be the order of a modulo n, then m divides n1 (first condition), but not (n1)/q (second condition). So q^{r} divides m which divides phi(n)a contradiction which proves the theorem.
What did we do in this proof? We looked at a group, (Z/nZ)*, which, if it had the correct size, n1, would show n was prime. We then collected enough information (the two conditions) to show the group had the correct size! This is the basis of all modern primality tests whether they are as simple as the test above or something as elaborate such as the methods using elliptic curves or number fields.
Theorem 1 requires a complete factorization of n1. The key to strengthening this result into a form that only requires the factored part of n1 to be roughly the square root of n1 was discovered by Pocklington:
Pocklington's Theorem (1914): Let n1 = q^{k}R where q is a prime which does not divide R. If there is an integer a such that a^{n}^{1} ≡ 1 (mod n) and gcd(a^{(n1)/q}1,n) = 1, then each prime factor p of n has the form q^{k}r+1.
Proof. Let p be any prime divisor of n, and let m be the order of a modulo p. As above m divides n1 (first condition on a), but not (n1)/q (second condition); so q^{k} divides m. Of course m divides p1 so the conclusion follows.
The result of applying Pocklington's theorem to each prime power factor of n (plus a little more work) is:
Theorem 2: Suppose n1 = FR, where F>R, gcd(F,R) is one and the factorization of F is known. If for every prime factor q of F there is an integer a>1 such thatthen n is prime.
 a^{n}^{1} ≡ 1 (mod n), and
 gcd(a^{(n1)/q}1,n) = 1;
(Notice that different a's can be used for each prime q.) Theorem 2 can be improved even more: if F<R, but either every factor of R is greater than sqrt(R/F); or n<2F^{3}, R=rF+s, 0<s<F, and r is odd or s^{2}4r is not a square; then n is prime. If you are interested in these theorems, then it is well worth going to the source: [BLS75].
Before we switch to the plus side tests, let me quote a few classical cases of theorem 2.
Pepin's Test (1877): Let F_{n} be the nth Fermat number (so F_{n} = ) with n>1. F_{n} is prime if and only if 3^{(Fn 1)/2} ≡ 1 (mod F_{n}).Proof. If 3^{(Fn1)/2} ≡ 1 (mod F_{n}), then F_{n} is prime by theorem 2 with a = 3. If instead F_{n} is prime, then 3^{(Fn1)/2} ≡ (3F_{n}) (mod F_{n}) where (3F_{n}) is the Jacobi symbol. It is easy to check that (3F_{n}) = 1.
Proth's Theorem (1878): Let n = h^{.}2^{k}+1 with 2^{k} > h. If there is an integer a such that a^{(n1)/2} ≡ 1 (mod n), then n is prime.
Theorem 3 ("Well Known"): Let n = h^{.}q^{k}+1 with q prime and q^{k} > h. If there is an integer a such that a^{n}^{1} ≡ 1 (mod n), and gcd(a^{(n1)/q}1,n) = 1, then n is prime.
Perhaps the best single source source of information on the classical tests is Hugh Williams book "Édouard Lucas and Primality Testing" [Williams98]. Other useful sources include "the" n^{2}1 article: [BLS75], and the standard surveys (such as [BLSTW88], [Ribenboim95] and [Riesel94]). These surveys include pointers to the results which use the factorization of other polynomials in n such as n^{6}1, most developed by Williams and his associates [Williams78, Williams98].
These theorems have been implemented and are available for you to use on most
computer platforms. For example, look at Yves Gallot's Proth.exe
and Chris Nash's PrimeForm).
