Proof of LL theorem

[Kevin]

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?

[Axel Fox]

http://www.utm.edu/research/primes/notes/proofs/LucasLehmer.html

[T.Rex]

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

[Numbers]

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?

[Dougy]

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.

[jinydu]

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.

[Numbers]

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?

[jinydu]

I guess they use different indices...

Prime95's help menu says that it starts with S_0 = 4

[Numbers]

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.

[ATH]

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?

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.

[jinydu]

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.