mersenneforum.org > Math Proof of LL theorem
 Register FAQ Search Today's Posts Mark Forums Read

 2003-07-11, 20:43 #1 Kevin     Aug 2002 Ann Arbor, MI 1B116 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?
 2003-07-11, 22:32 #2 Axel Fox     May 2003 25×3 Posts http://www.utm.edu/research/primes/notes/proofs/LucasLehmer.html
 2004-06-06, 16:59 #3 T.Rex     Feb 2004 France 22×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
 2005-08-17, 05:48 #4 Numbers     Jun 2005 Near Beetlegeuse 22·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 Lucas-Lehmer number denoted L_n where L_n = (L_n-1)^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?
 2005-08-17, 06:15 #5 Dougy     Aug 2004 Melbourne, Australia 2308 Posts Lucas-Lehmer Test: Let p be an odd prime. Then 2^p-1 is prime if and only if 2^p-1 divides L_{p-1}, where L_1=4 and L_{k+1}=L_{k}^2-2 1.) The test is both necessary and sufficient. 2.) L_n = x^{2^{n-1}} + y^{2^{n-1}} where x = 2+sqrt{3} and y=2-sqrt{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) 419-448. M. I. Rosen, A Proof of the Lucas-Lehmer Test, The American Mathematical Monthly 64 (1988) no. 9, 855-856. J. W. Bruce, A Really Trivial Proof of the Lucas-Lehmer Test, The American Mathematical Monthly 100 (1993) no. 4, 370-371.
 2005-08-17, 07:32 #6 jinydu     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.
 2005-08-18, 07:43 #7 Numbers     Jun 2005 Near Beetlegeuse 22·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 Lucas-Lehmer 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?
 2005-08-18, 10:56 #8 jinydu     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 2005-08-18 at 10:57
 2005-08-18, 14:04 #9 Numbers     Jun 2005 Near Beetlegeuse 18416 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.
2005-08-21, 11:53   #10
ATH
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_p-2 mod Mp. Perhaps this was the way the test was initially described and it stuck?

Quote:
 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?
If you check the first few terms in the sequence (Sloane's A003010) :

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^(3917-9) = 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 2005-08-21 at 11:59

2005-08-21, 13:29   #11
jinydu

Dec 2003
Hopefully Near M48

2×3×293 Posts

Quote:
 Originally Posted by ATH 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^(3917-9) = 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.
I don't think you have your numbers right, ATH. Remember, you're squaring with each step, so the number of digits doubles (or rather, almost doubles) with each step.

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.

 Similar Threads Thread Thread Starter Forum Replies Last Post McPogor Miscellaneous Math 18 2007-10-19 11:40 vtai Math 12 2007-06-28 15:34 bdodson Lounge 6 2007-03-19 17:19 mfgoode Puzzles 9 2006-09-27 16:37 jinydu Math 5 2005-05-21 16:52

All times are UTC. The time now is 03:18.

Wed May 12 03:18:48 UTC 2021 up 33 days, 21:59, 0 users, load averages: 2.05, 1.85, 1.62