Lucas-Lehmer primality test

The Lucas-Lehmer primality test is a method of testing the primality of some number n based on testing whether some other number is primitive modulo n.

If there exists some a less than n and greater than 1 such that firstly a^n-1≡1 and then

where q_i represents the prime factors of n-1, then n is prime, since this is the requirement for a to be primitive mod n, resulting then the multiplicative order of a mod n to be n-1.

For example, take n=71, n-1=70=(2)(5)(7). Take a=2 first:

This doesn't show that the order of 2 mod 70 is 1 because some factor of 70 may also work above. So check 70's factors:

So 2 is primitive mod 71 and thus 71 is prime.

If the factors of n-1 are not easily obtained, this method becomes difficult to use as these factors must be obtained in the a^(n-1)/q_i terms.

See also

• Edouard Lucas
• Lucas-Lehmer test
• Prime number