Re: Mersenne: Lehmer question
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
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: http://www.users.globalnet.co.uk/~aads/index.html Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Lehmer question
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
Mersenne: Lehmer question
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. For example, when p = 3, S[1] = 4 == 2^2 (mod 7). When p = 5, S[3] = 194 == 2^3 (mod 31). When p = 7, S[5] = 1416317954 == -2^4 (mod 127). The sign is + for p = 3 and p = 5 but - for p = 7. Do we have the pattern through M38? Peter Montgomery Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
