examples of the Lucas-Lehmer primality test on small numbers
To illustrate the Lucas-Lehmer primality test for Mersenne numbers, it is best to use small numbers. For any purpose other than pedagogical, applying this test to a small number is of course more trouble than it’s worth, since it would be much easier to just perform integer factorization; a classic example of “sandblasting a soup cracker,” in Scott Adams’ words. But for the purpose of illustrating the test, since the numbers in the recurrence relation get quite large, small numbers are more suitable.
Is a Mersenne prime? The first few terms of the recurrence relation (with initial term ) are 4, 14, 194, 37634, 1416317954, 2005956546822746114, 4023861667741036022825635656102100994, etc. (see A003010 in Sloane’s OEIS). For our first example, we need to look up , which is 14. That number divided by 7 is 2, telling us that 7 is indeed a Mersenne prime.
Is a Mersenne prime? and that divides neatly by 127, being 15794933439549182 times 127. So 127 is indeed a Mersenne prime. Already this is larger than what a typical pocket scientific calculator can handle with integer precision.
What about 11? is 687296824066442772388374862317475309242471541086466717521926185830884874057909 579647328830691025610434367796639355951720423573065949163446060745647128680782 876080552030246583594390175808839109786661858757174155410844949265004751673811 68505927378181899753839260609452265365274850901879881203714, which divided by 2047 gives a remainder of 1736, telling us that 2047 is a Mersenne number but not a Mersenne prime. Even by computer it would have been quicker to perform trial division on 2047, giving the result . But already for , with its least prime factor being 179951, the 16336th prime, the Lucas-Lehmer test appears much more attractive than trial division.
|Title||examples of the Lucas-Lehmer primality test on small numbers|
|Date of creation||2013-03-22 17:45:40|
|Last modified on||2013-03-22 17:45:40|
|Last modified by||PrimeFan (13766)|