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
