Finding primes & proving primality 3.1: n-1 tests and Pepin's tests for Fermats Home > Primality Proving > Chapter Three > n-1 Tests

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 p-1 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 n-1.  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 n-1 there is an integer a such that

• a^n-1 ≡ 1 (mod n), and
• a^(n-1)/q is not 1 (mod n);

then n is prime.

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 theorem--since in this case you must be taking me at my word anyway.)

Proof: To show n is prime we need only show phi(n) = n-1 (here phi(n) is Euler totient function), or more simply, that n-1 divides phi(n).  Suppose this is not the case, then there is a prime q and exponent r>0 such that q^r divides n-1, 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 n-1 (first condition), but not (n-1)/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, n-1, 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 n-1.  The key to strengthening this result into a form that only requires the factored part of n-1 to be roughly the square root of n-1 was discovered by Pocklington:

Pocklington's Theorem (1914):  Let n-1 = q^kR 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^(n-1)/q-1,n) = 1, then each prime factor p of n has the form q^kr+1.

Proof.  Let p be any prime divisor of n, and let m be the order of a modulo p.  As above m divides n-1 (first condition on a), but not (n-1)/q (second condition); so q^k divides m.  Of course m divides p-1 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 n-1 = 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

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

then n is prime.

(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³, R=rF+s, 0<s<F, and r is odd or s²-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^{(F_n -1)/2} ≡ -1 (mod F_n).

Proof.  If  3^(F_n-1)/2 ≡ -1 (mod F_n), then F_n is prime by theorem 2 with a = 3.  If instead F_n is prime, then 3^(F_n-1)/2 ≡ (3|F_n) (mod F_n) where (3|F_n)  is the Jacobi symbol.  It is easy to check that (3|F_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^(n-1)/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^(n-1)/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²-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⁶-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).