mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2003-07-11, 20:43   #1
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

1B116 Posts
Default 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?
Kevin is offline   Reply With Quote
Old 2003-07-11, 22:32   #2
Axel Fox
 
Axel Fox's Avatar
 
May 2003

25×3 Posts
Default

http://www.utm.edu/research/primes/notes/proofs/LucasLehmer.html
Axel Fox is offline   Reply With Quote
Old 2004-06-06, 16:59   #3
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

22×229 Posts
Default 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
T.Rex is offline   Reply With Quote
Old 2005-08-17, 05:48   #4
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

22·97 Posts
Default 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?
Numbers is offline   Reply With Quote
Old 2005-08-17, 06:15   #5
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

2308 Posts
Default

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.
Dougy is offline   Reply With Quote
Old 2005-08-17, 07:32   #6
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2×3×293 Posts
Default

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.
jinydu is offline   Reply With Quote
Old 2005-08-18, 07:43   #7
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

22·97 Posts
Default

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?
Numbers is offline   Reply With Quote
Old 2005-08-18, 10:56   #8
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2×3×293 Posts
Default

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
jinydu is offline   Reply With Quote
Old 2005-08-18, 14:04   #9
Numbers
 
Numbers's Avatar
 
Jun 2005
Near Beetlegeuse

18416 Posts
Default

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.
Numbers is offline   Reply With Quote
Old 2005-08-21, 11:53   #10
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

31·101 Posts
Default

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
ATH is online now   Reply With Quote
Old 2005-08-21, 13:29   #11
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2×3×293 Posts
Default

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.
jinydu is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Proof of Fermat's Last Theorem McPogor Miscellaneous Math 18 2007-10-19 11:40
help with a proof vtai Math 12 2007-06-28 15:34
Proof (?!) that RH is false? bdodson Lounge 6 2007-03-19 17:19
A proof with a hole in it? mfgoode Puzzles 9 2006-09-27 16:37
A Second Proof of FLT? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.