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 $M_{3}=2^{3}-1=7$ a Mersenne prime? The first few terms of the recurrence relation $s_{n}={s_{n-1}}^{2}-2$ (with initial term $s_{1}=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 $s_{3-1}$ , which is 14. That number divided by 7 is 2, telling us that 7 is indeed a Mersenne prime.

Is $M_{7}=2^{7}-1=127$ a Mersenne prime? $s_{6}=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? $s_{10}$ is 68729682406644277238837486231747530924247154108646671752192618583088487405790957964732883069102561043436779663935595172042357306594916344606074564712868078287608055203024658359439017580883910978666185875717415541084494926500475167381168505927378181899753839260609452265365274850901879881203714, 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 $2047=23\\times 89$ . But already for $M_{59}$ , with its least prime factor being 179951, the 16336th prime, the Lucas-Lehmer test appears much more attractive than trial division.

How does the test work on a composite number, say 4? Seeing that $s_{3}=194\\equiv 14\\mod 15$ (or $-1\\mod 15$ if you prefer), it is quite obvious that 15 is not a Mersenne prime.

单词	ExamplesOfTheLucasLehmerPrimalityTestOnSmallNumbers
释义	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 $M_{3}=2^{3}-1=7$ a Mersenne prime? The first few terms of the recurrence relation $s_{n}={s_{n-1}}^{2}-2$ (with initial term $s_{1}=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 $s_{3-1}$ , which is 14. That number divided by 7 is 2, telling us that 7 is indeed a Mersenne prime. Is $M_{7}=2^{7}-1=127$ a Mersenne prime? $s_{6}=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? $s_{10}$ is 68729682406644277238837486231747530924247154108646671752192618583088487405790957964732883069102561043436779663935595172042357306594916344606074564712868078287608055203024658359439017580883910978666185875717415541084494926500475167381168505927378181899753839260609452265365274850901879881203714, 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 $2047=23\\times 89$ . But already for $M_{59}$ , with its least prime factor being 179951, the 16336th prime, the Lucas-Lehmer test appears much more attractive than trial division. How does the test work on a composite number, say 4? Seeing that $s_{3}=194\\equiv 14\\mod 15$ (or $-1\\mod 15$ if you prefer), it is quite obvious that 15 is not a Mersenne prime.
随便看	proof of fundamental theorem of finitely generated abelian groups ProofOfFundamentalTheoremOfGaloisTheory proof of fundamental theorem of Galois theory ProofOfFundamentalTheoremOfSymmetricPolynomials proof of fundamental theorem of symmetric polynomials proof of {f⁢(t)-f⁢(s)}/{t-s}≤{f⁢(u)-f⁢(s)}/{u-s}≤{f⁢(u)-f⁢(t)}/{u-t} for convex f ProofOfGaloisGroupOfTheCompositumOfTwoGaloisExtensions proof of Galois group of the compositum of two Galois extensions ProofOfGaussDigammaTheorem ProofOfGaussianMaximizesEntropyForGivenCovariance proof of Gaussian maximizes entropy for given covariance ProofOfGaussMeanValueTheorem proof of Gauss’ digamma theorem proof of Gauss’ mean value theorem ProofOfGelfandNaimarkRepresentationTheorem proof of Gelfand-Naimark representation theorem ProofOfGelfandSpectralRadiusTheorem proof of Gelfand spectral radius theorem ProofOfGeneralAssociativity proof of general associativity ProofOfGeneralizationOfTheParallelogramLaw proof of generalization of the parallelogram law ProofOfGeneralizedLeibnizRule proof of generalized Leibniz rule ProofOfGeneralizedRuizsIdentity