20030711, 20:43  #1 
Aug 2002
Ann Arbor, MI
1B1_{16} Posts 
Proof of Lucas Lehmer test
Everywhere I look, all I can find is an explanation of the Lucas Lehmer test, but no proof of it. Does anybody know where I can the proof?

20030711, 22:32  #2 
May 2003
2^{5}×3 Posts 
http://www.utm.edu/research/primes/notes/proofs/LucasLehmer.html

20040606, 16:59  #3 
Feb 2004
France
2^{2}×229 Posts 
Ribenboim's book
Hi Kevin,
You should buy the very good book of Ribenboim: little book of bigger primes. It contains a very good description of the theory of LLT. Some other books present only what is needed for proving LLT for Mersenne Primes. Ribenboim's book presents the general theory. It's very hard to understand, but very interesting. If you speak French, you could also look at Lucas' book. I've started looking at it: it seems to contain some more results not available in Ribenboim's book. The proof on utm.edu is good but limited to Mersenne's primes. Tony 
20050817, 05:48  #4 
Jun 2005
Near Beetlegeuse
2^{2}·97 Posts 
LL test
As I understand it, a Mersenne number 2^p –1 is prime only if it divides a second number called a LucasLehmer number denoted L_n where
L_n = (L_n1)^2 –2. So that, for example, L_5 / 2^5 –1 = 37634 / 31 = 1214 and this division is the LL test. Two questions: 1. Is passing the test sufficient to prove primality, or is it merely necessary? 2. Is there a way to calculate a specific LL number, L_3917 for example, without starting at the beginning of the sequence and calculating each one in turn? 
20050817, 06:15  #5 
Aug 2004
Melbourne, Australia
230_{8} Posts 
LucasLehmer Test: Let p be an odd prime. Then 2^p1 is prime if and only if 2^p1 divides L_{p1}, where L_1=4 and L_{k+1}=L_{k}^22
1.) The test is both necessary and sufficient. 2.) L_n = x^{2^{n1}} + y^{2^{n1}} where x = 2+sqrt{3} and y=2sqrt{3}. I don't know of any others. Lucas proved the sufficiency of this, in 1878, for when p was a prime = 1 (mod 4). Lehmer proved, in 1930, both the necessity and sufficiency of this test, and that it applied to all odd prime exponents. See the following for proofs: D. H. Lehmer, An Extended Theory of Lucas' Functions, Annals of Mathematics, 31 (1930) 419448. M. I. Rosen, A Proof of the LucasLehmer Test, The American Mathematical Monthly 64 (1988) no. 9, 855856. J. W. Bruce, A Really Trivial Proof of the LucasLehmer Test, The American Mathematical Monthly 100 (1993) no. 4, 370371. 
20050817, 07:32  #6 
Dec 2003
Hopefully Near M48
2×3×293 Posts 
Thus, it is possible to write down the end result of the LL test (after all the iterations have completed) straight away. Unfortunately, the number you get at the end is so large that, as far as I know, it is not possible to test whether the exponent is a divisor of this very large number.
That's why we still have to go through all the iterations of the LL test: to keep the number small enough to work with... Please correct me if I am wrong. 
20050818, 07:43  #7 
Jun 2005
Near Beetlegeuse
2^{2}·97 Posts 
Dougy,
Thank you for a very clear and full answer to my question. I am still a little confused though. I read about this in Marcus du Sautoy’s “Music of the Primes”, where he says, “… the test gets going when n = 3 and the corresponding LucasLehmer number is L_3 = 14.” Which seems clear enough. But when I plug 3 into the formula you give I get 194, which according to du Sautoy is L_4. As I consider it unlikely that either of you are wrong, I have clearly misunderstood something. Any ideas? 
20050818, 10:56  #8 
Dec 2003
Hopefully Near M48
2×3×293 Posts 
I guess they use different indices...
Prime95's help menu says that it starts with S_0 = 4 Last fiddled with by jinydu on 20050818 at 10:57 
20050818, 14:04  #9 
Jun 2005
Near Beetlegeuse
184_{16} Posts 
Yes, you’re right. It would seem that different people are using the subscript to mean different things. George’s help screen in Prime95 says s_0 = 4, and Mathworld says the same thing. Sloanes Encyclopedia says essentially the same thing calling it a_0 = 4 where they are using the subscript to count the terms in the sequence where, in the curious logic of mathematics, the first term is numbered 0. Very logical.
Du Sautoy is using his subscript to indicate the exponent of the Mersenne number being tested. So when he says L_3 = 14, he means that this is the LL number with which to test 2^3 – 1 for primality. Also very logical. Dougy’s formula gives the nth term in the sequence where, in this context, n = 0 has no meaning so the first term is therefore n = 1. Also very logical. In fact I can’t even figure out what there was to be confused about. Not. 
20050821, 11:53  #10  
Einyen
Dec 2003
Denmark
31·101 Posts 
It's just a matter of definition. If you use S_0=4 you need to check S_p2 mod Mp. Perhaps this was the way the test was initially described and it stuck?
Quote:
4,14,194,37634,1416317954,2005956546822746114,4023861667741036022825635656102100994, 16191462721115671781777559070120513664958590125499158514329308740975788034 S_7 or L_9 as you call it allready has 74 digits and they (almost) double each step. So L_3917 would have almost 74*2^(39179) = 2*10^1178 digits. That means the number describing the number of digits in L_3917 would itself have 1179 digits!!! So its not too practical to calculate this sequence without doing mod Mp :) It gets much worse around S_30000000 like used in LL tests :) The number of digits in S_30000000 is itself over 9million digits. Last fiddled with by ATH on 20050821 at 11:59 

20050821, 13:29  #11  
Dec 2003
Hopefully Near M48
2×3×293 Posts 
Quote:
Therefore, the 30 millionth step would have roughly 2^(30 million) digits, or about 10^(9 million) digits, which is MUCH more than 9 million digits. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Proof of Fermat's Last Theorem  McPogor  Miscellaneous Math  18  20071019 11:40 
help with a proof  vtai  Math  12  20070628 15:34 
Proof (?!) that RH is false?  bdodson  Lounge  6  20070319 17:19 
A proof with a hole in it?  mfgoode  Puzzles  9  20060927 16:37 
A Second Proof of FLT?  jinydu  Math  5  20050521 16:52 