20120203, 02:23  #1 
Feb 2012
2 Posts 
Can zero be an "intermediate step" value in LucasLehmer?
When going through the P2 recursions to determine if 2^P1 is prime using LucasLehmer, is it possible that you can get zero as a value before the (P2)th step? Are there any known examples of this?
I already realize that if 0 is an intermediate step, then the number cannot be prime (since the next step is 0^2  2 = (N2) mod N, then (N2)^2  2 = 2 mod N, and 2^2  2 = 2 mod N, so there will never be a zero term). 
20120203, 07:41  #2  
Dec 2007
Cleves, Germany
529_{10} Posts 
Quote:


20120203, 09:18  #3  
"Nathan"
Jul 2008
Maryland, USA
5·223 Posts 
Quote:


20120203, 09:28  #4  
Jun 2003
13×359 Posts 
Quote:


20120203, 10:37  #5 
Sep 2005
127 Posts 
Since every factor of a Mersenne number is of the form 2kp+1 [p being the exponent] same reasoning applies for composites, no?
J 
20120203, 10:39  #6 
Sep 2005
127 Posts 

20120203, 10:54  #7 
Sep 2005
127 Posts 

20120203, 11:41  #8 
"Nathan"
Jul 2008
Maryland, USA
5·223 Posts 

20120203, 12:55  #9 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
If Mp is prime, then it is not possible. We know the order of the group is Mp+1, so is 2^p, and the starting element is chosen to be a nonsquare in the group, so it likewise has order 2^p. Reaching zero means reaching the element of order 2 sooner than after p1 squarings, contradicting the above.
If Mp is composite, I think it is possible, but exceedingly unlikely. It would require that for each prime factor q of Mp, the order of the starting element in F_q[sqrt(3)] is the same power of 2. It may be possible to construct such composites, for example for P1 (i.e., not in a quadratic extension), the order of 2 modulo 319489 and 974849 is 4096, so you'd see a residue of 1 (the element of order 2) after 11 squarings. The probability that all prime factors of some Mp are of this kind is practically 0, perhaps provably 0. Last fiddled with by akruppa on 20120203 at 12:57 
20120203, 15:31  #10 
Aug 2006
11·13·41 Posts 
Just for kicks I checked: there are no small examples (p < 10^4).

20120203, 18:02  #11 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
Well any such test would also have residue of 2, so you could check all verified tests in PrimeNet.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Penultimate LucasLehmer step  maxal  Math  45  20181219 23:32 
AouessareEl HaddouchiEssaaidi "test": "if Mp has no factor, it is prime!"  wildrabbitt  Miscellaneous Math  11  20150306 08:17 
"one step backward _two steps forward "  devarajkandadai  Miscellaneous Math  10  20130820 12:57 
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?  nitai1999  Software  7  20040826 18:12 