proof the lucas lehmer test

[kurtulmehtap]

Dear All,
The last iteration of The Lucas Lehmer requires:
(Sn^2 - 2)mod(2^n - 1) =0
In other form :
Sn^2 = k (2^n - 1)

I wonder if there is only one pair of Sn and k for the given n.
If there is only one k and Sn can someone provide a formal proof?
Sorry, I am an engineer not a math guy.

[R.D. Silverman]

Originally Posted by kurtulmehtap

Dear All,
The last iteration of The Lucas Lehmer requires:
(Sn^2 - 2)mod(2^n - 1) =0 [sic]
In other form :
Sn^2 = k (2^n - 1) [sic]; this is wrong.

I wonder if there is only one pair of Sn and k for the given n.
If there is only one k and Sn can someone provide a formal proof?
Sorry, I am an engineer not a math guy.

Sorry, but I can't make sense of your question. The value of k
is irrelevant. And I don't know what you might mean about a
different possible S_n. One has no control over the value of S_n.
It's value is determined recursively from the initial seed and the
value of 2^n-1.

And your specification for the actual test is wrong as well.

Are you asking about a different initial seed? The answer to that
question is yes. Other seed values than 4 can be used. But changing
the seed is irrelevant to either the speed of the test or determining
if 2^n-1 is prime.

What are youREALLY asking?

[philmoore]

I believe that what you mean to say is that S_n-1=k(2ⁿ-1), where the sequence S_m is defined as S₁=4 and S_m=(S_m-1)²-2 for m>1. If 2ⁿ-1 is prime, we do not get S_m a multiple of 2ⁿ-1 until the (n-1)-st step, is that what you are asking? You could take a look at the proof on the Mersennewiki: http://www.mersennewiki.org/index.php/Lucas-Lehmer_Test

[TimSorbet]

I'm pretty sure he's asking (translated to modular arithmetic terms) if a step in the LL test will result in a 0, and then if you were to continue the LL sequence, if it would result in a 0 again. Or, as he put it, if there is ever more than one Sn and k pair for a given p such that Sn = k(2^p-1).
Here is the answer to that: There is only one such Sn and k pair for any given LL sequence, which is clear from looking at the next few lines if you were to continue after you reach 0 mod 2^p-1.

Sm = 0 mod 2^n-1
residue is 0 (if n is prime and m=n-2, then you've just completed the LL test and 2^n-1 is prime)

S(m+1) = (0^2 - 2) mod 2^n-1 = -2 mod 2^n-1
residue is -2

S(m+2) = ((-2)^2 - 2) mod 2^n-1 = 2 mod 2^n-1
residue is 2

S(m+3) = (2^2 - 2) mod 2^n-1 = 2 mod 2^n-1
residue is 2

S(m+4) = (2^2 - 2) mod 2^n-1 = 2 mod 2^n-1
residue is 2
...
Since it continues as 2 infinitely once you reach 0, you can never reach 0 again. (and in case you're curious, like me, the result is the same whether you consider the -2 residue to simply be -2 or to be (2^p-1)-2=2^p-3)

[kurtulmehtap]

Here is an example to explain my stupid question:
Take the last iteration of the Lucas lehmer Test for 127
((111)^2 -2) mod 127 = 0
In other words
(111)^2 - 2= 97*127 Here Sn =111 and k=97.

However there's also
(16)^2 -2 = 2*127 here Sn=16 and k=2

I know that 111 is the correct residual and 16 is the wrong one.

I was asking if there are other combinations of Sn and k (16-2 and 111-97 for 127) for a given n. And is there a formal proof

Originally Posted by R.D. Silverman

Sorry, but I can't make sense of your question. The value of k
is irrelevant. And I don't know what you might mean about a
different possible S_n. One has no control over the value of S_n.
It's value is determined recursively from the initial seed and the
value of 2^n-1.

And your specification for the actual test is wrong as well.

Are you asking about a different initial seed? The answer to that
question is yes. Other seed values than 4 can be used. But changing
the seed is irrelevant to either the speed of the test or determining
if 2^n-1 is prime.

What are youREALLY asking?

[R.D. Silverman]

Originally Posted by kurtulmehtap

Here is an example to explain my stupid question:
Take the last iteration of the Lucas lehmer Test for 127
((111)^2 -2) mod 127 = 0
In other words
(111)^2 - 2= 97*127 Here Sn =111 and k=97.

However there's also
(16)^2 -2 = 2*127 here Sn=16 and k=2

I know that 111 is the correct residual and 16 is the wrong one.

I was asking if there are other combinations of Sn and k (16-2 and 111-97 for 127) for a given n. And is there a formal proof

Your entire question is wrong headed. It isn't that "16 is the wrong one".
There are infinitely many integers x such that x^2-2 = 0 mod 2^n-1.

You don't get to SELECT S_{n-1] as an input to the test.

S_k is determined RECURSIVELY from S_{k-1}; with S_0 = 4.

And the value of k (as you use it) is totally irrelevant.

[ATH]

The value of your k gets so large so fast its hard to comprehend. For a 45,000,000 test where the "frontwave" of LL-testing is atm, your k is around 10^{10[sup]13,500,000}[/sup]. That means the number of digits in k, is itself a number with 13,500,000 digits.

I found out (not proven though) that when 2^p-1 is prime, your k is 2*(c*2^p-1) where c is another enormous odd number. So that the final step which you call Sn, which is actually called S_n-2 if you start with S₀=4 is:
S_p-2 = (2^p-1)*2*(c*2^p-1)

but only when 2^p-1 is prime, and if you start with S₀=4.

[TimSorbet]

Originally Posted by ATH

The value of your k gets so large so fast its hard to comprehend. For a 45,000,000 test where the "frontwave" of LL-testing is atm, your k is around 10^{10[sup]13,500,000}[/sup]. That means the number of digits in k, is itself a number with 13,500,000 digits.

I found out (not proven though) that when 2^p-1 is prime, your k is 2*(c*2^p-1) where c is another enormous odd number. So that the final step which you call Sn, which is actually called S_n-2 if you start with S₀=4 is:
S_p-2 = (2^p-1)*2*(c*2^p-1)

but only when 2^p-1 is prime, and if you start with S₀=4.

M127's penultimate LL step is 2^64.
(2^64)^2-2=2^128-2
2^128-2=2*M127=k
So if k=c*2^p-1, then
2*(2^127-1)=c*2^127-1
2^128-2=c*2^127-1
2^128-1=c*2^127
But M127 doesn't divide M128, so c isn't an integer. Perhaps it was supposed to be k=c*(2^p-1)? Trying that...
2*(2^127-1)=c*(2^127-1)
2=c
But c is supposed to be odd, and enormous. There's definitely something wrong here.
Maybe you meant in the case that you don't reduce modulo Mp each iteration. Let's try that with M7=2^7-1=127. With S0=4 and S(n+1)=Sn^2-2, S5 is 2005956546822746114. 2005956546822746114=2*127*7897466719774591. Bingo, that's it! I wouldn't imagine a proof of that would be terribly difficult, assuming it always holds true...

[ATH]

Originally Posted by Mini-Geek

M127's penultimate LL step is 2^64.
(2^64)^2-2=2^128-2
2^128-2=2*M127=k
So if k=c*2^p-1, then
2*(2^127-1)=c*2^127-1
2^128-2=c*2^127-1
2^128-1=c*2^127
But M127 doesn't divide M128, so c isn't an integer. Perhaps it was supposed to be k=c*(2^p-1)? Trying that...
2*(2^127-1)=c*(2^127-1)
2=c
But c is supposed to be odd, and enormous. There's definitely something wrong here.
Maybe you meant in the case that you don't reduce modulo Mp each iteration. Let's try that with M7=2^7-1=127. With S0=4 and S(n+1)=Sn^2-2, S5 is 2005956546822746114. 2005956546822746114=2*127*7897466719774591. Bingo, that's it! I wouldn't imagine a proof of that would be terribly difficult, assuming it always holds true...

That's right I meant without the modulo step, like the OP also meant. I tested my "theory" 2.5 years ago up to 2³¹-1 directly and up to M₂₈ = 2^86,243 - 1 by doing mod (2*M_p*2^p) and mod (4*M_p*2^p):
http://www.mersenneforum.org/showpos...5&postcount=21
http://www.mersenneforum.org/showpos...5&postcount=33
http://www.mersenneforum.org/showpos...5&postcount=34

[R.D. Silverman]

Originally Posted by ATH

That's right I meant without the modulo step, like the OP also meant. I tested my "theory" 2.5 years ago up to 2³¹-1 directly and up to M₂₈ = 2^86,243 - 1 by doing mod (2*M_p*2^p) and mod (4*M_p*2^p):
http://www.mersenneforum.org/showpos...5&postcount=21
http://www.mersenneforum.org/showpos...5&postcount=33
http://www.mersenneforum.org/showpos...5&postcount=34

So let's get back to the original question. What was the O.P. really
looking for???

[m_f_h]

Originally Posted by R.D. Silverman

So let's get back to the original question. What was the O.P. really
looking for???

To oversimplify a bit: I think he essentially wanted to know whether there are 2 different x such that x^2-2 = 0 (in Z/qZ).

Of course, if x is a solution, then -x is a solution too; e.g. 16 = -111 in Z_127.