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 relationMathworldPlanetmath get quite large, small numbers are more suitable.

Is M3=23-1=7 a Mersenne prime? The first few terms of the recurrence relation sn=sn-12-2 (with initial term s1=4) are 4, 14, 194, 37634, 1416317954, 2005956546822746114, 4023861667741036022825635656102100994, etc. (see A003010 in Sloane’s OEIS). For our first example, we need to look up s3-1, which is 14. That number divided by 7 is 2, telling us that 7 is indeed a Mersenne prime.

Is M7=27-1=127 a Mersenne prime? s6=2005956546822746114 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? s10 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 divisionMathworldPlanetmath on 2047, giving the result 2047=23×89. But already for M59, with its least prime factorMathworldPlanetmath being 179951, the 16336th prime, the Lucas-Lehmer test appears much more attractive than trial division.

How does the test work on a composite numberMathworldPlanetmath, say 4? Seeing that s3=19414mod15 (or -1mod15 if you prefer), it is quite obvious that 15 is not a Mersenne prime.

Title examples of the Lucas-Lehmer primality test on small numbers
Canonical name ExamplesOfTheLucasLehmerPrimalityTestOnSmallNumbers
Date of creation 2013-03-22 17:45:40
Last modified on 2013-03-22 17:45:40
Owner PrimeFan (13766)
Last modified by PrimeFan (13766)
Numerical id 5
Author PrimeFan (13766)
Entry type Example
Classification msc 11A51