LucasLehmer primality test
The
LucasLehmer 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^{n1}≡1 and then

where
q_{i} represents the prime factors of
n1, 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
n1.
For example, take n=71, n1=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 n1 are not easily obtained, this method becomes difficult to use as these factors must be obtained in the a^{(n1)/qi} terms.