
Theorem 1: Let n > 1. If for every prime factor q of n1 there is an integer a such thatWe 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.)then n is prime.
 a^{n}^{1} = 1 (mod n), and
 a^{(n1)/q} is not 1 (mod n);
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.
The result of applying Pocklington's theorem to each prime power factor of n (plus a little more work) is: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.
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 that(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].then n is prime.
 a^{n}^{1} = 1 (mod n), and
 gcd(a^{(n1)/q}1,n) = 1;
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^{(Fn1)/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. Look at our list of links
to programs (especially Yves Gallot's Proth.exe
and Chris Nash's PrimeForm).
