1,1

Such primes are the exceptional p for which x^2 = -2 mod p has a solution, as x^2 = -2 mod p is soluble for *every* p with ord_p(-2) odd. But if ord_p(-2) is even and p-1=2^r.j with j odd, then x^2 = -2 mod p is soluble if and only if ord_p(-2) is not divisible by 2^r.

More generally, the equation x^(2^k) =-2 mod p has a solution iff either ord_p(-2) is odd or ( p = 1 mod 2^(k+1) and ord_p(-2) is even but not divisible by 2^(r-k+1)).

Proof: Choose primitive root g mod p with -2 = g^a mod p, where a=(p-1)/ord_p(-2). Writing x = g^u, see that solving x^(2^k) = -2 mod p is equivalent to solving 2^k.u + (p-1).v = a for some integers u,v.

A necessary and sufficient condition for this is that gcd(2^k,p-1) | a. So for p-1 = 2^r.j, j odd and ord_p(-2) = 2^s.h, h odd, condition becomes min(k,r) <= r-s. If s = 0 (ie ord_p(-2) odd) this is always valid; for positive s we need k < r-s+1, or s < r-k+1.

17 belongs to this sequence as 7^2 = -2 mod 17 and ord_p(-2) = 8, even but <> 0 mod 16.

with(numtheory):k:=1: A:=NULL:p:=2: for c to 30000 do p:=nextprime(p); o:=order(-2, p); R:=gcd(2^100, p-1); if o mod 2=0 and p mod 2^(k+1) = 1 and o mod R/2^(k-1)<>0 then A:=A, p; ; fi; od:A;

Cf. A033203 (all p for which x^2 = -2 mod p has a solution); .

Cf. A163183 (p with ord_p(-2) odd): a subsequence of A033203, whose complement in A163183 is the current sequence.

Sequence in context: A004625 A141174 A007519 this_sequence A138005 A166147 A028886

Adjacent sequences: A163182 A163183 A163184 this_sequence A163186 A163187 A163188

easy,nonn

Chris Smyth (c.smyth(AT)ed.ac.uk), Jul 23 2009