Re: Mersenne: Lehmer question

[Bill Daly]

Peter-Lawrence.Montgomery wrote:

>Problem A3 in Richard Guy's `Unsolved Problems in Number Theory'
>includes this question, by D.H. Lehmer:
>
>Let Mp = 2^p - 1 be a Mersenne prime, where p > 2.
>Denote S[1] = 4 and  S[k+1] = S[k]^2 - 2 for k >= 1.
>Then S[p-2] == +- 2^((p+1)/2) mod Mp.
>Predict which congruence occurs.

Of course, the reason that S[p-2] == +- 2^((p+1)/2) mod Mp is that we
know that S[p-1] == 0 mod Mp, and S[p-1] = S[p-2]^2 - 2, thus S[p-2] is
a square root of 2 mod Mp. Then since 2^p == 1 mod Mp, 2^(p+1) == 2 mod
Mp, thus +- 2^((p+1)/2) are the square roots of 2 mod Mp, and S[p-2]
must be congruent to one of these mod Mp.

I don't see any easy way of predicting the sign, but the following might
be helpful.

We know that it is possible to use a value other than 4 for S[1] in the
LL sequence, e.g. we can set S[1] = 10 instead. Suppose that b is such
that if we set S[1] = b, then S[p-1] == 0 mod Mp. The necessary and
sufficient condition that b have this property is that b-2 is a
quadratic residue mod Mp and b+2 is a quadratic nonresidue mod Mp.

It turns out that there are exactly 2^(p-2) = (Mp+1)/4 values b which
have this property, and there is a systematic way of generating them.
Let L[0] = 2, L[1] = 4, L[j+2] = 4*L[j+1] - L[j]. (The sequence L[j] is
related to the sequence S[k] with S[1] = 4 by the following identity:
S[k] = L[2^(k-1)].) Let B[j] = L[2*j-1] for j = 1..2^(p-2). Then the
values B[j] mod Mp are all distinct, and each B[j] has the desired
property.

Of this set B[j], exactly half correspond to S[p-2] == +2^((p+1)/2) mod
Mp, and the other half correspond to S[p-2] == -2^((p+1)/2) mod Mp. The
two subsets are the set B1[j] = B[j] for j = 0,1,4,5 mod 8, and the set
B2[j] = B[j] for j = 2,3,6,7 mod 8. 4, which is B[1], belongs to B1. I
do not know which of the sets B1 and B2 corresponds to the + sign for
S[p-2]. Note that B[2] = 52 belongs to B2, thus the sequences beginning
with S[1] = 4 and S[1] = 52 have opposite signs for S[p-2].

The above, with a few modifications, also works for primes of the form
c*2^n - 1, where c > 1 is odd and n is not necessarily prime. Suppose
that q = c*2^n - 1 is prime. Let b be such that b-2 is a quadratic
residue mod q and b+2 is a quadratic nonresidue mod q. Let L[0] = 2,
L[1] = b, L[j+2] = b*L[j+1] - L[j]. Let B[j] = L[c*(2*j-1)] for j =
1..2^(n-2). Let S[1] = B[j], S[k+1] = S[k]^2 - 2. Then S[p-1] == 0 mod
q, and S[p-2] is a square root of 2 mod q. Exactly half of the B[j]
correspond to a specific value of S[p-2]. The subsets B1 and B2 can be
defined in the same way as for the case c = 1.

Regards,

Bill
**
This email and any files transmitted with it are confidential and
intended solely for the use of the individual or entity to whom
they are addressed.
This footnote also confirms that this email message has been swept by
MIMEsweeper for the presence of computer viruses.
**

Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm

Re: Mersenne: Lehmer question

[Andy Steward]

Dear All,

Following up my own msg here.

First, there is an obvious linear relationship between my two
conjectures, so they are equivalent.

Second, predictions where possible (U=Unknown):

p (p+1)/2 mod 31 Conj 1 (p-2) mod 31 Conj 2
4423 11  U 19  U
9689 9  - 15  -
9941 11  U 19  U
11213 27  U 20  U
19937 18  U 2  U
21701 1  U 30  U
23209 11  U 19  U
44497 22  U 10  U
86243 1  U 30  U
110503 10  - 17  -
132049 26  U 18  U
216091 11  U 19  U
756839 3  + 3  +
859433 26  U 18  U
1257787 28  - 22  -
1398269 23  - 12  -
2976221 18  U 2  U
3021377 28  - 22  -
6972593 6  U 9  U

Regards,
Andy Steward


Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm

Re; Mersenne: Lehmer question

[Andy Steward]

>Let Mp = 2^p - 1 be a Mersenne prime, where p > 2.
>Denote S[1] = 4 and  S[k+1] = S[k]^2 - 2 for k >= 1.
>Then S[p-2] == +- 2^((p+1)/2) mod Mp.
>Predict which congruence occurs.

Dear Peter and All,

This is as far as I can go in Ubasic:

p Result
3 +
5 +
7 -
13 +
17 -
19 -
31 +
61 +
89 -
107 -
127 +
521 -
607 -
1279 -
2203 +
2281 -
3217 -
4253 +


The algebra suggests two values to consider

1) Consider q=((p+1)/2) mod n

Taking the p pairwise where signs differ eliminates the following
possible n:
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,
28,29,30,32,33,34,35,36,37,38,39,40,42,43,45,46,47,48,49,51,52,54,55,57,
58,59,60,61,63,64,66,67,72,73,74,75,77,78,80,81,84,86,87,89,91,96,99,103,
104,111,114,115,120,122,125,126,127,129,131,133,144,146,151,154,156,162,
169,177,178,182,183,185,189,192,193,197,203,208,211,222,225,230,231,240,
245,254,258,259,262,263,266,267,273,288,297,301,302,309,311,312,319,347,
353,359,364,366,370,375,378,399,462,493,507,515,518,524,526,531,534,546,
549,555,567,569,576,609,622,624,633,637,638,691,694,706,789,798,801,803,
841,933,986,1041,1048,1057,1059,1077,1092,1093,1098,1110,1125,1134,1138,
1139,1487,1545,1578,1593,1602,1606,1607,1823,1866,2073,2082,2117,2118,
2123

That first gap at 31 is interesting...
Conjecture:
 take ((p+1)/2) mod 31
 if in (0,2,3,7,16,17,19) then sign(S[p-2]) = +
 if in (4,9,10,13,14,20,23,25,28) then sign(S[p-2]) = -
 if in (1,5,6,8,11,12,15,18,21,22,24,26,27,29,30,31) then no data


2) Consider q=(p-2) mod n
Taking the p pairwise where signs differ eliminates the following
possible n:
2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,
28,29,30,32,33,34,35,36,37,38,39,40,42,43,44,45,46,47,48,49,50,51,52,54,
55,56,57,58,59,60,61,63,64,66,67,68,70,72,73,74,75,76,77,78,80,81,84,86,
87,89,90,91,92,94,96,98,99,102,103,104,108,110,111,114,115,116,118,120,
122,125,126,127,128,129,131,132,133,134,144,146,148,150,151,154,156,160,
162,168,169,172,174,177,178,182,183,185,189,192,193,197,198,203,206,208,
211,222,225,228,230,231,240,244,245,250,252,254,258,259,262,263,266,267,
273,288,292,297,301,302,308,309,311,312,319,324,338,347,353,354,356,359,
364,366,370,375,378,384,386,394,399,406,416,422,444,450,460,462,480,490,
493,507,508,515,516,518,524,526,531,532,534,546,549,555,567,569,576,594,
602,604,609,618,622,624,633,637,638,691,694,706,718,728,732,740,750,756,
789,798,801,803,841,924,933,986,1014,1030,1036,1041,1048,1052,1057,1059,
1062,1068,1077,1092,1093,1098,1110,1125,1134,1138,1139,1152,1218,1244,
1248,1266,1274,1276,1382,1388,1412,1487,1545,1578,1593,1596,1602,1606,
1607,1682,1823,1866,1972,2073,2082,2096,2114,2117,2118,2123,2154,2184,
2186,2196,2220,2250,2268,2276,2278,2974,3090,3156,3186,3204,3212,3214,
3646,3732,4146,4164,4234,4236,4246

Again a gap at n=31
Conjecture:
 take (p-2) mod 31
 if in (0,1,3,4,11,28,29) then sign(S[p-2]) = +
 if in (5,6,12,15,16,17,22,23,25) then sign(S[p-2]) = -
 if in (2,7,8,9,10,13,14,18,19,20,21,24,26,27,30,31) then no data

It's all a bit thin and arm-waving, but I would be interested to see if
a continuation of the series confirms or denies either of these
conjectures.


Regards,
Andy Steward
Factorisations of generalised repunits at:





Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm