20090929, 11:14  #1 
Sep 2009
24_{16} 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. 
20090929, 12:22  #2  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×937 Posts 
Quote:
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^n1. 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^n1 is prime. What are youREALLY asking? 

20090929, 12:23  #3 
"Phil"
Sep 2002
Tracktown, U.S.A.
2^{5}×5×7 Posts 
I believe that what you mean to say is that S_{n1}=k(2^{n}1), where the sequence S_{m} is defined as S_{1}=4 and S_{m}=(S_{m1})^{2}2 for m>1. If 2^{n}1 is prime, we do not get S_{m} a multiple of 2^{n}1 until the (n1)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/LucasLehmer_Test

20090929, 12:35  #4 
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^p1).
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^p1. Sm = 0 mod 2^n1 residue is 0 (if n is prime and m=n2, then you've just completed the LL test and 2^n1 is prime) S(m+1) = (0^2  2) mod 2^n1 = 2 mod 2^n1 residue is 2 S(m+2) = ((2)^2  2) mod 2^n1 = 2 mod 2^n1 residue is 2 S(m+3) = (2^2  2) mod 2^n1 = 2 mod 2^n1 residue is 2 S(m+4) = (2^2  2) mod 2^n1 = 2 mod 2^n1 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^p1)2=2^p3) Last fiddled with by MiniGeek on 20090929 at 12:45 
20090929, 12:46  #5  
Sep 2009
2^{2}·3^{2} 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 (162 and 11197 for 127) for a given n. And is there a formal proof Quote:


20090929, 12:53  #6  
"Bob Silverman"
Nov 2003
North of Boston
16510_{8} Posts 
Quote:
There are infinitely many integers x such that x^22 = 0 mod 2^n1. You don't get to SELECT S_{n1] as an input to the test. S_k is determined RECURSIVELY from S_{k1}; with S_0 = 4. And the value of k (as you use it) is totally irrelevant. 

20090929, 14:05  #7 
Einyen
Dec 2003
Denmark
5×683 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 LLtesting 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_{n2} if you start with S_{0}=4 is: S_{p2} = (2^{p}1)*2*(c*2^{p}1) but only when 2^{p}1 is prime, and if you start with S_{0}=4. Last fiddled with by ATH on 20090929 at 14:09 
20090929, 15:23  #8  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
11×389 Posts 
Quote:
(2^64)^22=2^1282 2^1282=2*M127=k So if k=c*2^p1, then 2*(2^1271)=c*2^1271 2^1282=c*2^1271 2^1281=c*2^127 But M127 doesn't divide M128, so c isn't an integer. Perhaps it was supposed to be k=c*(2^p1)? Trying that... 2*(2^1271)=c*(2^1271) 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^71=127. With S0=4 and S(n+1)=Sn^22, 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... 

20090930, 00:55  #9  
Einyen
Dec 2003
Denmark
5×683 Posts 
Quote:
http://www.mersenneforum.org/showpos...5&postcount=21 http://www.mersenneforum.org/showpos...5&postcount=33 http://www.mersenneforum.org/showpos...5&postcount=34 

20091001, 12:56  #10  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·937 Posts 
Quote:
looking for??? 

20091001, 20:43  #11  
Feb 2007
2^{4}·3^{3} Posts 
Quote:
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 20091001 at 20:45 

Thread Tools  
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  20180311 23:20 
A second proof for the LucasLehmer Test  carpetpool  Miscellaneous Math  2  20170730 09:21 
LucasLehmer test proof etc.  science_man_88  Miscellaneous Math  48  20100714 23:33 
LucasLehmer Test  storm5510  Math  22  20090924 22:32 
LucasLehmer Test proof  alpertron  mersennewiki  16  20060318 07:23 