On Feb 14, 2007 10:44 AM, Kurt Foster <
drsardonicus@...> wrote:
> The Lucas-Lehmer test uses the fundamental unit in Q(sqrt(3)), and applies to every
> odd prime exponent. There is a similar test in Q(sqrt(p)) for any prime p congruent
> to 3 (mod 8). But for p > 3 it seems "obvious" that the test will automatically be
> inapplicable to any exponent l congruent to k (mod p-1) for some k relatively prime
> to p-1. The problem can be restated as follows: If d is the multiplicative order of 2
> (mod p) [d divides p-1], then at least one of
>
> 2^k - 1 (mod p) for (k, d) = 1
>
> is a quadratic non-residue (mod p). (I'd expect about half of them to be non-
> residues, but no obvious candidate comes to mind!)
>
> Where can I find a proof?
For odd d the proof is simple:
We have
(2^d-1) - (2^2-1) = 2^2 (2^(d-2)-1)
and
-1 == 2^2 (2^(d-2)-1) / (2^2-1) (mod p).
Since -1 is not a square modulo p, the numbers (2^(d-2)-1) and (2^2-1)
cannot be squares modulo p at the same time. Hence, either k=2 or
k=d-2 gives a required quadratic non-residue.
Regards,
Max
