Inspiration for LL Test?

JHagerson · 2005-09-21, 04:10

I will freely admit that I am an engineer, not a math major. I have taken the math progression for engineers (algebra in junior high school, geometry, algebra II, trigonometry, and 2 semesters of calculus in high school, another semester of calculus, differential equations, and statistics in college), but that was many years ago. Therefore, if the answer to this question is on the blackboard the first day of Introduction to Ring Theory, I freely admit that I have never taken that class.

As I understand it, the LL test that M_x is prime involves testing if M_x is a factor of the number S_x, where, as it has been flogged to death elsewhere in these forums, the full numeric presentation of even "small" terms of S_x is impossible within our universe.

Here is my question. What provided the inspiration for this test? It seems counterintuitive (to me, one of the Uninitiated) to test for primality using this method (as if one wanted to go South, but looked North and discovered the Great Polar Circle).

If the answer to my question is so obvious as to waste everyone's time, please just state that the answer is left as an exercise and leave it at that. Thank you.

Dougy · 2005-09-21, 06:11

The Lucas-Lehmer test wasn't really invented, rather than discovered. The LL-test came as a result of the study of Lucas sequences. Lucas also discovered the closed-form formula for the Fibonacci numbers using these sequences, namely $F_n=\frac{(\frac{(1+\sqrt{5})}{2})^n-(\frac{(1-\sqrt{5})}{2})^n}{\sqrt{5}}$ .

For a proof that doesn't use fancy algebra: D. H. Lehmer, An Extended Theory of Lucas' Functions, Annals of Mathematics, 1930.

jinydu · 2005-09-21, 06:18

Quote:

Originally Posted by Dougy

Lucas also discovered the closed-form formula for the Fibonacci numbers using these sequences

Really? It wasn't known until Lucas' time?

philmoore · 2005-09-21, 15:40

Actually, the closed form of Fibonacci numbers had been discovered a few years earlier, I believe by an Italian, but I don't have the reference at hand to check. An interesting account of how Lucas was led from a study of the divisibility properties of the Fibonacci sequence to his investigation of the Lucas sequences is given in:

Williams, Hugh C., Édouard Lucas and Primality Testing, John Wiley & Sons, 1998

R.D. Silverman · 2005-09-21, 15:46

Quote:

Originally Posted by JHagerson

Here is my question. What provided the inspiration for this test?

The analagous test for p-1, as opposed to p+1.

T.Rex · 2005-09-21, 20:52

Quote:

Originally Posted by R.D. Silverman

The analagous test for p-1, as opposed to p+1.

??? Unclear for me. Can you elaborate ?

To answer question of JHagerson:

Quote:

What provided the inspiration for this test?

Miss Anne-Marie Decaillot-Laulagnet, in his thesis about Edouard Lucas written in 1999 (in French), says at the beginning of Chapter 8 that Eugène Catalan provided a result the 3 of March 1861 about "a recurrent serie which general term is or is not divisible by n when n is prime or not". This was a serie of order 3. We do not know if Lucas read this.
Lucas was mainly inspired by the work of Fibonacci. He traveled to Italia in order to read the original papers.
The first important result of Lucas is that "there is a law of apparition of prime numbers in the Fibonacci serie".

If you want to know how the history of primality tests began, you should read HC Williams' book "Edouard Lucas and Primality Testing".

Also, note that the LLT can also be used to test primality of other kinds of numbers, like Fermat numbers.

Tony

trilliwig · 2005-09-23, 06:16

Quote:

Originally Posted by T.Rex

??? Unclear for me. Can you elaborate ?

Compare Theorem 1 here with Theorem 4 there.

--
Sam

T.Rex · 2005-09-23, 07:45

Quote:

Originally Posted by trilliwig

Compare Theorem 1 here with Theorem 4 there.

OK. It is what I was thinking Mr Silverman was talking about.

Dividing between [n-1 tests/Pépin test/N+1 numbers] and [n+1 tests/LLT/N-1 numbers] is wrong.

I don't know if there are N-1 numbers that can be proved prime with a Pépin's test like (I should read again Williams' book), but it is sure that there are N+1 numbers that can be proved prime by means of a LLT-like test: Fermat numbers.

Just have a look to Williams' book or (if you don't have access to it) read my papers Two theorems for proving the primality of Fermat numbers, based on Lucas Sequences. and A LLT-like test for proving the primality of Fermat numbers, based on Lucas Sequences. .

The problem is that so few people have read Williams' book and so many have read Ribenboim's book (which says a mistake about Lucas Sequences -Chapter 2.V on top of page 63- ) that nearly every one thinks like Silverman.

If Mr Silverman would like to read Williams' book or my papers and provide his opinion in this thread, that would help.

Regards,

Tony

maxal · 2005-10-03, 22:16

Quote:

Originally Posted by philmoore

Actually, the closed form of Fibonacci numbers had been discovered a few years earlier, I believe by an Italian, but I don't have the reference at hand to check.

This formula is called Binet's formula. According to MathWorld,
It was derived by Binet in 1843, although the result was known to Euler, Daniel Bernoulli, and de Moivre more than a century earlier.

2005-09-21, 04:10	#1
JHagerson May 2005 Naperville, IL, USA 2²·7² Posts	Inspiration for LL Test? I will freely admit that I am an engineer, not a math major. I have taken the math progression for engineers (algebra in junior high school, geometry, algebra II, trigonometry, and 2 semesters of calculus in high school, another semester of calculus, differential equations, and statistics in college), but that was many years ago. Therefore, if the answer to this question is on the blackboard the first day of Introduction to Ring Theory, I freely admit that I have never taken that class. As I understand it, the LL test that M_x is prime involves testing if M_x is a factor of the number S_x, where, as it has been flogged to death elsewhere in these forums, the full numeric presentation of even "small" terms of S_x is impossible within our universe. Here is my question. What provided the inspiration for this test? It seems counterintuitive (to me, one of the Uninitiated) to test for primality using this method (as if one wanted to go South, but looked North and discovered the Great Polar Circle). If the answer to my question is so obvious as to waste everyone's time, please just state that the answer is left as an exercise and leave it at that. Thank you.

2005-09-21, 15:40	#4
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 3·373 Posts	Actually, the closed form of Fibonacci numbers had been discovered a few years earlier, I believe by an Italian, but I don't have the reference at hand to check. An interesting account of how Lucas was led from a study of the divisibility properties of the Fibonacci sequence to his investigation of the Lucas sequences is given in: Williams, Hugh C., Édouard Lucas and Primality Testing, John Wiley & Sons, 1998 Last fiddled with by philmoore on 2005-09-21 at 15:41

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing	Trilo	Miscellaneous Math	25	2018-03-11 23:20
New PC test re-test plan?	dh1	Information & Answers	8	2015-12-11 11:50
Double check LL test faster than first run test	lidocorc	Software	3	2008-12-03 15:12
Will the torture test, test ALL available memory?	swinster	Software	2	2007-12-01 17:54
A primality test for Fermat numbers faster than Pépin's test ?	T.Rex	Math	0	2004-10-26 21:37

2005-09-21, 06:11	#2
Dougy Aug 2004 Melbourne, Australia 2³·19 Posts	The Lucas-Lehmer test wasn't really invented, rather than discovered. The LL-test came as a result of the study of Lucas sequences. Lucas also discovered the closed-form formula for the Fibonacci numbers using these sequences, namely $F_n=\frac{(\frac{(1+\sqrt{5})}{2})^n-(\frac{(1-\sqrt{5})}{2})^n}{\sqrt{5}}$ . For a proof that doesn't use fancy algebra: D. H. Lehmer, An Extended Theory of Lucas' Functions, Annals of Mathematics, 1930.