 mersenneforum.org > Math proof the lucas lehmer test
 Register FAQ Search Today's Posts Mark Forums Read  2009-09-29, 11:14 #1 kurtulmehtap   Sep 2009 22·32 Posts proof the lucas lehmer test 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.   2009-09-29, 12:22   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23×3×313 Posts Quote:
 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.

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.   2009-09-29, 12:23 #3 philmoore   "Phil" Sep 2002 Tracktown, U.S.A. 25·5·7 Posts I believe that what you mean to say is that Sn-1=k(2n-1), where the sequence Sm is defined as S1=4 and Sm=(Sm-1)2-2 for m>1. If 2n-1 is prime, we do not get Sm a multiple of 2n-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   2009-09-29, 12:35 #4 TimSorbet Account Deleted   "Tim Sorbera" Aug 2006 San Antonio, TX USA 11×389 Posts 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) Last fiddled with by TimSorbet on 2009-09-29 at 12:45   2009-09-29, 12:46   #5
kurtulmehtap

Sep 2009

3610 Posts 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

Quote:
 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?   2009-09-29, 12:53   #6
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23·3·313 Posts Quote:
 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.   2009-09-29, 14:05 #7 ATH Einyen   Dec 2003 Denmark 32·383 Posts 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 1010[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 2p-1 is prime, your k is 2*(c*2p-1) where c is another enormous odd number. So that the final step which you call Sn, which is actually called Sn-2 if you start with S0=4 is: Sp-2 = (2p-1)*2*(c*2p-1) but only when 2p-1 is prime, and if you start with S0=4. Last fiddled with by ATH on 2009-09-29 at 14:09   2009-09-29, 15:23   #8
TimSorbet
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

11×389 Posts Quote:
 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 1010[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 2p-1 is prime, your k is 2*(c*2p-1) where c is another enormous odd number. So that the final step which you call Sn, which is actually called Sn-2 if you start with S0=4 is: Sp-2 = (2p-1)*2*(c*2p-1) but only when 2p-1 is prime, and if you start with S0=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...   2009-09-30, 00:55   #9
ATH
Einyen

Dec 2003
Denmark

32×383 Posts Quote:
 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 231-1 directly and up to M28 = 286,243 - 1 by doing mod (2*Mp*2p) and mod (4*Mp*2p):
http://www.mersenneforum.org/showpos...5&postcount=21
http://www.mersenneforum.org/showpos...5&postcount=33
http://www.mersenneforum.org/showpos...5&postcount=34   2009-10-01, 12:56   #10
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23×3×313 Posts Quote:
 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 231-1 directly and up to M28 = 286,243 - 1 by doing mod (2*Mp*2p) and mod (4*Mp*2p): 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???   2009-10-01, 20:43   #11
m_f_h

Feb 2007

24·33 Posts Quote:
 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.

Last fiddled with by m_f_h on 2009-10-01 at 20:45   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Trilo Miscellaneous Math 25 2018-03-11 23:20 carpetpool Miscellaneous Math 2 2017-07-30 09:21 science_man_88 Miscellaneous Math 48 2010-07-14 23:33 storm5510 Math 22 2009-09-24 22:32 alpertron mersennewiki 16 2006-03-18 07:23

All times are UTC. The time now is 14:59.

Tue Mar 28 14:59:09 UTC 2023 up 222 days, 12:27, 0 users, load averages: 0.59, 0.78, 0.85