I am trying to understand the generalized LucasLehmer algorithm, but I have encountered a problem.
According to Wikipedia, this is how the eneralized LucasLehmer test for primality works:
"In computational number theory, the LucasLehmer test is a primality test for a natural number n; it requires that the prime factors of n  1 be already known.
If for every prime factor q of n  1 there exists an integer a less than n and greater than 1 such that firstly
a^(n1) = 1 (mod n)
and then
a^((n1)/q} = 1 (mod n)
then n is prime. If no such number a can be found, then n is composite number."
Let's see how this works for the case n = 11, which we know is prime. In this case, the prime
factors of n  1 are q = 2 and 5. For q = 2, the values of a which satisfy the two conditions
a^(n1) = 1 (mod n)
and
a^((n1)/q} = 1 (mod n)
are a = 3, 4, 5, and 9.
For q = 5, the only value of a which satisfy these two conditions is a = 10. This demonstrates
that sometimes (at least) one value of a will not suffice for all factors of n  1. So, in general, we need to find a value a for each factor.
Now, let's see how this works for the case n = 57, which we know is composite (57 = 3 * 19).
The prime factors of n  1 are 2 and 7 in this case. The values a = 20 and 37 satisfy the two
conditions
a^(n1) = 1 (mod n)
and
a^((n1)/q} = 1 (mod n)
for both factors q = 2 and 7. Therefore 57 is prime? What is wrong?
Here are the arithmetic details:
a = 20, q = 2:
20^56 = 1 (mod 57) because
56 = 8 + 16 + 32
20^2 = 1 (mod 57)
20^4 = 1 (mod 57)
20^8 = 1 (mod 57)
20^16 = 1 (mod 57)
20^32 = 1 (mod 57)
20^56 = 20^8 * 20^16 * 20^32 = 1 (mod 57)
and
20^(56/2} = 1 (mod 57) because
56/2 = 28 = 4 + 8 + 16
20^28 = 20^4 * 20^8 * 20^16 = 1 (mod 57)
a = 20, q = 7:
20^56 = 1 (mod 57)
and
20^(56/7} = 1 (mod 57) because
56/7 = 8
20^8 = 1 (mod 57)
a = 37, q = 2:
37^56 = 1 (mod 57) because
56 = 8 + 16 + 32
37^2 = 1 (mod 57)
37^4 = 1 (mod 57)
37^8 = 1 (mod 57)
37^16 = 1 (mod 57)
37^32 = 1 (mod 57)
37^56 = 37^8 * 37^16 * 37^32 = 1 (mod 57)
and
37^(56/2} = 1 (mod 57) because
56/2 = 28 = 4 + 8 + 16
37^28 = 37^4 * 37^8 * 37^16 = 1 (mod 57)
a = 37, q = 7:
37^56 = 1 (mod 57)
and
37^(56/7} = 1 (mod 57) because
56/7 = 8
37^8 = 1 (mod 57)
____________
