Proof of LL theorem

[T.Rex]

Numbers,
If you are interested in the LLT and its history, you should read the books of Paulo Ribenboim (A little book for bigger primes) and of HC. Williams (Edouard Lucas and Primality Testing). They provide many very interesting information about the Maths behind the LLT.
Regards,
Tony

[cheesehead]

Originally Posted by ATH

The number of digits in S_30000000 is itself over 9million digits.

Originally Posted by jinydu

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.

That's just what ATH meant: there are over 9 million (decimal) digits in the number whose value is the number of (decimal) digits in S_30000000.

Restated: Let NDD_30000000 be the number of decimal digits in S_30000000. Then there are over 9 million decimal digits in the value of NDD_30000000.

You're both right.

[Citrix]

Originally Posted by Numbers

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?

Yes there is, you need 2 things

1) An understanding of FFT (Extremely complicated to explain; actually a modification of FFT)
2) Lots and lots of memory to store the decimal digits.

Citrix

[cheesehead]

Originally Posted by Citrix

1) An understanding of FFT (Extremely complicated to explain; actually a modification of FFT)

No, neither the Fast Fourier Transform nor an understanding of it is required to calculate the values of Lucas numbers.

The FFT is simply a tool used to speed up the calculations, not something essential to the Lucas algorithm. (You'll notice that Lucas never mentions FFT in his explanation.)

[Citrix]

Originally Posted by cheesehead

No, neither the Fast Fourier Transform nor an understanding of it is required to calculate the values of Lucas numbers.

The FFT is simply a tool used to speed up the calculations, not something essential to the Lucas algorithm. (You'll notice that Lucas never mentions FFT in his explanation.)

An LL-test doesn't require FFT. I know that.
What I am saying is that LL3154 etc can be generated without generating LL1,LL2 ... LL3154 using a modification of FFT. Though the complexity would be the same as 3154 multiplications.

[philmoore]

There was an earlier thread that requested a proof of Lehmer's theorem that the Lucas-Lehmer test is a necessary and sufficient condition for the primality of 2^p-1 without using group theory. I have tried to distill the essence of the papers by Rosen and Bruce in The American Mathematical Monthly and have posted a proof on the Mersenne-wiki at:
http://www.mersennewiki.org/index.php/Lucas-Lehmer_Test
Unfortunately, although the proof seems to be one of the simplest around in terms of required background in number theory, it does not give one the insight that a proof using more advanced abstract algebra gives. As usual in mathematics, abstraction often enables one to distinguish between characteristics of a particular problem and more general principles with wider applicability. Still, it is a nice proof, and the sufficiency requires almost no background at all, while the necessity requires application of quadratic reciprocity. Feel free to edit it if you can come up with improvements.

[Numbers]

Originally Posted by philmoore

Still, it is a nice proof, ...

You can certainly say that again. I have spent two days studying it, and a very rewarding two days it has been. Thank you very much indeed.

[Run800]

Can anyone provide a simple (nothing much above first year calculus level) way to explain the proof of the LL theorem? I understand the theorem easily, but I don't fully understand the whole proof.

edit: I'd appreciate it if you could also give a relatively simple explaination of FFTs.

[R.D. Silverman]

Originally Posted by Run800

Can anyone provide a simple (nothing much above first year calculus level) way to explain the proof of the LL theorem? I understand the theorem easily, but I don't fully understand the whole proof.

edit: I'd appreciate it if you could also give a relatively simple explaination of FFTs.

The QUESTION ITSELF is "wrong-headed".

The mathematics involved in the proof involves nothing more than
simple theorems in elementary group theory and number theory, plus a little
knowledge of finite fields. This body of knowledge does not lie "above"
calculus. Indeed, it requires no knowledge of calculus at all. However,
it does involve *elementary* mathematics that is not usually seen before
college.

So let me ask: How much number theory and group theory do you know?
How much algebra do you know? Calculus is irrelevant. I can give a
very short proof (less than 10 lines), but it requires knowing Lagrange's
Theorem, and some stuff about multiplicative sub-groups of a finite field.

The mathematics involved isn't more "advanced" than 1st year calculus.
It is merely different.

[John Renze]

Originally Posted by Run800

Can anyone provide a simple (nothing much above first year calculus level) way to explain the proof of the LL theorem? I understand the theorem easily, but I don't fully understand the whole proof.

"Nothing much above first year calculus level" has a plain meaning that I understood immediately.

As Bob said, there is a simple explanation, but it involves some abstract algebra that you might not know. It is possible to prove the LL test directly by simpler means, but it involves some messy and non-obvious modular arithmetic. This is likely the dilemma you are facing.

John

[alpertron]

Run800,

You can start reading the Lucas-Lehmer test on MersenneWiki and write here your questions.