| Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |
| Topics | Help • Register • News • History • How to • Sequences statistics • Template prototypes |
Difference between revisions of "Residue"
(restored) |
m |
||
| Line 1: | Line 1: | ||
| − | 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 [[ | + | 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>\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. | The residue is the end result of the long calculation of the L-L test. When the numbers being tested are large: <math>\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. | ||
| Line 15: | Line 15: | ||
==External links== | ==External links== | ||
| − | *[ | + | *[[Wikipedia:Residue_number_system|Wikipedia]] |
[[Category:Math]] | [[Category:Math]] | ||
Latest revision as of 10:24, 6 February 2019
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.
