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 an-1≡1 and then
For example, take n=71, n-1=70=(2)(5)(7). Take a=2 first:
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)/qi terms.