Residue

The Lucas-Lehmer test, like division, at the end produces a remainder of sorts, it is called the residue or residual. And like division, if the remainder/residue is zero there is a special (but different) meaning. For division a zero remaindert means that the number is exactly divisible. For the L-L test a zero residue means that the number is prime.

The residue is the end result of the long calculation of the L-L test. When the numbers being tested are large: [math]\displaystyle{ \gt2^{64}-1 }[/math] (i.e. exponents larger than 64) and above, the residue is 16 hexadecimal digits or longer. To ensure that no errors caused a Mersenne prime to be missed and that there cofidence in the results GIMPS is set-up to double check all L-L tests. To clear an exponent two matching residues must be reported. For two test to produced matching erroneaous residues (meaning they both missed a prime) out of a pool of ~ 18.4 pentillion numbers, this is considered to be impossible.

Mathematicians are interested in these residues. It is not practical for GIMPS to have the full length residues stored and sent to PrimeNet.

Example

Here is the Lucas test for [math]\displaystyle{ 2^7-1 }[/math], which is 127:

S0 = 4

S1 = (4 * 4 - 2) mod 127 = 14

S2 = (14 * 14 - 2) mod 127 = 67

S3 = (67 * 67 - 2) mod 127 = 42

S4 = (42 * 42 - 2) mod 127 = 111

S5 = (111 * 111 - 2) mod 127 = 0 <- the residue for this test; 127 is prime.

External links

• Wikipedia