Lucas-Lehmer Test proof

alpertron · 2005-12-07, 19:22

I was reading more carefully to the Lucas-Lehmer Test proof presented in the Mersennewiki and I found that it is not a proof at all.

After the introduction there is the sentence "We are assuming that $S_{p-1}$ is divisible by $2^p-1$ . "

If we compute S₁ = 4, ..., until S_p-1 = 0 we know that it is prime because we are assuming it (?????)

philmoore · 2005-12-07, 22:05

Quote:

Originally Posted by alpertron

I was reading more carefully to the Lucas-Lehmer Test proof presented in the Mersennewiki and I found that it is not a proof at all.

After the introduction there is the sentence "We are assuming that $S_{p-1}$ is divisible by $2^p-1$ . "

If we compute S₁ = 4, ..., until S_p-1 = 0 we know that it is prime because we are assuming it (?????)

There are two parts to the proof. One part is to show that if $2^p-1$ is prime, then $S_{p-1}$ is divisible by $2^p-1$ . The other part of the proof is to show that if $S_{p-1}$ is divisible by $2^p-1$ , then $2^p-1$ is prime. Because this second part guarantees that candidates passing the Lucas-Lehmer test are actually prime, and because it assumes very little background in number theory, I placed it first. Notice that the conclusion of this paragraph is that $2^p-1$ is prime. It guarantees that composite numbers will always fail the Lucas-Lehmer test, but doesn't necessarily prove that all prime numbers pass it. The proof that all prime numbers pass the L-L test is the point of the third paragraph. It does require a little knowledge of quadratic reciprocity, and was placed last for that reason.

alpertron · 2005-12-08, 17:06

So the proof is OK, but the paragraphs are reversed. I think the last paragraph should be first, so after that we can safely assume that S_p-1 because it was proved in the previous paragraph.

philmoore · 2005-12-08, 22:05

Perhaps the second and third paragraphs should be labeled "Proof of Sufficiency" and "Proof of Necessity". There is no logical reason that either paragraph must come before the other because the two proofs are logically independent; i.e, neither depends upon the results of the other. However, each proof does make use of the set of numbers $a+b\sqrt 3 mod Q$ , and if you find a compelling pedagogical reason to switch the paragraphs, you certainly have my permission.

alpertron · 2005-12-09, 20:42

I exchanged the proofs and also replaced in Rosen's proof the letter Q by F, because the variable Q was used in Bruce's proof as 2^p - 1, so it is clear that they are different values.

philmoore · 2005-12-09, 21:44

Thanks, the main problem that I see is that the properties of the numbers $a+b\sqrt 3 mod Q$ are not discussed until the sufficiency proof, but these properties actually get used in the necessity proof. Also the phrase "From the previous proof" in the second sentence of the sufficiency proof needs to be removed. The sufficiency proof does not depend at all on the necessity proof, and this phrase is extremely misleading. Sufficiency means that if the L-L test is satisfied for some prime exponent p, then 2^p - 1 is prime. Necessity means that if 2^p - 1 is prime, then the L-L test is satisfied. Each proof is completely independent of the other. Unfortunately, the necessity proof now seems very unclear, because much of the notation that is used there does not get introduced until the second proof. If I get time over school break, I may try to fix this.

alpertron · 2005-12-09, 23:42

I still fail to see why the proof of sufficiency does not depend on the other proof, since it starts assuming the "output" of the proof of necessity: $S_{p-1}$ is multiple of $2^p-1$ .

It appears that the text should be reworked a bit. I will continue reading it.

T.Rex · 2005-12-10, 15:43

Alpertron,
Have you tried to read Ribenboim's proof of LLT ? It appears in page 77 and 78 (but requires to read many pages before ...).
I prefer this proof, though it is longer.
Tony

alpertron · 2005-12-10, 18:35

I added some steps to the proof and now it is "crystal clear" to me.

philmoore · 2005-12-11, 01:10

Suppose one proved that if a, b, and c are the lengths of the sides of a right triangle with c the side opposite the right angle, then a²+b²=c². Now suppose one proved that if a, b, and c are the lengths of the sides of any triangle and a²+b²=c², then the angle opposite the side of length c must be a right angle. Even though the second proof starts by assuming the formula proven in the first proof, one cannot say in general that the second proof depends on the first. Each of the theorems assumes as input the output of the other theorem. The two theorems are converses, and in general, a theorem may be true even though the converse theorem may be false. Of course, in some cases, the proof of a converse may be dependent on the truth of the original theorem, and Euclid does in fact prove the converse to the Pythagorean theorem by SSS congruence using the Pythagorean theorem itself (Book I, theorems 47 and 48), but I challenge you to show me where the proof of sufficiency of the Lucas-Lehmer tests depends upon the proof of necessity. The fact that there is some common notation between the two proofs may have confused you, but look at the sufficiency proof alone: it simply says that IF S_p-1 is divisible by 2^p-1, THEN 2^p-1 is prime. The statement that S_p-1 is divisible by 2^p-1 is the supposition of the theorem, and in no way is justified by the necessity piece, which assumed that 2^p-1 is prime anyway. Here we cannot assume this, it is what must be proven.

alpertron · 2005-12-11, 21:15

Arggghhh!!! I was wrong, the fact that $S_{p-1}$ is divisible by $2^p-1$ , is the hypotesis of the proof.

I changed the wording again. Please let me know if there are errors.

2005-12-07, 19:22	#1
alpertron Aug 2002 Buenos Aires, Argentina 5D7₁₆ Posts	Lucas-Lehmer Test proof I was reading more carefully to the Lucas-Lehmer Test proof presented in the Mersennewiki and I found that it is not a proof at all. After the introduction there is the sentence "We are assuming that $S_{p-1}$ is divisible by $2^p-1$ . " If we compute S₁ = 4, ..., until S_p-1 = 0 we know that it is prime because we are assuming it (?????)

2005-12-10, 15:43	#8
T.Rex Feb 2004 France 3×311 Posts	Proof of LLT by Ribenboim Alpertron, Have you tried to read Ribenboim's proof of LLT ? It appears in page 77 and 78 (but requires to read many pages before ...). I prefer this proof, though it is longer. Tony

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
A second proof for the Lucas-Lehmer Test	carpetpool	Miscellaneous Math	2	2017-07-30 09:21
Lucas-Lehmer test proof etc.	science_man_88	Miscellaneous Math	48	2010-07-14 23:33
proof the lucas lehmer test	kurtulmehtap	Math	13	2009-10-02 12:12
Lucas-Lehmer Test	storm5510	Math	22	2009-09-24 22:32

2005-12-08, 17:06	#3
alpertron Aug 2002 Buenos Aires, Argentina 1495₁₀ Posts	So the proof is OK, but the paragraphs are reversed. I think the last paragraph should be first, so after that we can safely assume that S_p-1 because it was proved in the previous paragraph.

2005-12-08, 22:05	#4
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 2⁵×5×7 Posts	Perhaps the second and third paragraphs should be labeled "Proof of Sufficiency" and "Proof of Necessity". There is no logical reason that either paragraph must come before the other because the two proofs are logically independent; i.e, neither depends upon the results of the other. However, each proof does make use of the set of numbers $a+b\sqrt 3 mod Q$ , and if you find a compelling pedagogical reason to switch the paragraphs, you certainly have my permission.

2005-12-09, 20:42	#5
alpertron Aug 2002 Buenos Aires, Argentina 5D7₁₆ Posts	I exchanged the proofs and also replaced in Rosen's proof the letter Q by F, because the variable Q was used in Bruce's proof as 2^p - 1, so it is clear that they are different values.

2005-12-09, 21:44	#6
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 2⁵×5×7 Posts	Thanks, the main problem that I see is that the properties of the numbers $a+b\sqrt 3 mod Q$ are not discussed until the sufficiency proof, but these properties actually get used in the necessity proof. Also the phrase "From the previous proof" in the second sentence of the sufficiency proof needs to be removed. The sufficiency proof does not depend at all on the necessity proof, and this phrase is extremely misleading. Sufficiency means that if the L-L test is satisfied for some prime exponent p, then 2^p - 1 is prime. Necessity means that if 2^p - 1 is prime, then the L-L test is satisfied. Each proof is completely independent of the other. Unfortunately, the necessity proof now seems very unclear, because much of the notation that is used there does not get introduced until the second proof. If I get time over school break, I may try to fix this.

2005-12-09, 23:42	#7
alpertron Aug 2002 Buenos Aires, Argentina 5D7₁₆ Posts	I still fail to see why the proof of sufficiency does not depend on the other proof, since it starts assuming the "output" of the proof of necessity: $S_{p-1}$ is multiple of $2^p-1$ . It appears that the text should be reworked a bit. I will continue reading it.

2005-12-10, 18:35	#9
alpertron Aug 2002 Buenos Aires, Argentina 5·13·23 Posts	I added some steps to the proof and now it is "crystal clear" to me.

2005-12-11, 01:10	#10
philmoore "Phil" Sep 2002 Tracktown, U.S.A. 2⁵×5×7 Posts	Suppose one proved that if a, b, and c are the lengths of the sides of a right triangle with c the side opposite the right angle, then a²+b²=c². Now suppose one proved that if a, b, and c are the lengths of the sides of any triangle and a²+b²=c², then the angle opposite the side of length c must be a right angle. Even though the second proof starts by assuming the formula proven in the first proof, one cannot say in general that the second proof depends on the first. Each of the theorems assumes as input the output of the other theorem. The two theorems are converses, and in general, a theorem may be true even though the converse theorem may be false. Of course, in some cases, the proof of a converse may be dependent on the truth of the original theorem, and Euclid does in fact prove the converse to the Pythagorean theorem by SSS congruence using the Pythagorean theorem itself (Book I, theorems 47 and 48), but I challenge you to show me where the proof of sufficiency of the Lucas-Lehmer tests depends upon the proof of necessity. The fact that there is some common notation between the two proofs may have confused you, but look at the sufficiency proof alone: it simply says that IF S_p-1 is divisible by 2^p-1, THEN 2^p-1 is prime. The statement that S_p-1 is divisible by 2^p-1 is the supposition of the theorem, and in no way is justified by the necessity piece, which assumed that 2^p-1 is prime anyway. Here we cannot assume this, it is what must be proven.

2005-12-11, 21:15	#11
alpertron Aug 2002 Buenos Aires, Argentina 5×13×23 Posts	Arggghhh!!! I was wrong, the fact that $S_{p-1}$ is divisible by $2^p-1$ , is the hypotesis of the proof. I changed the wording again. Please let me know if there are errors.