

A163185


Primes p such that the equation x^2 = 2 mod p has a solution, and ord_p(2) is even.


2



17, 41, 73, 89, 97, 113, 137, 193, 233, 241, 257, 313, 337, 353, 401, 409, 433, 449, 457, 521, 569, 577, 593, 601, 641, 673, 761, 769, 809, 857, 881, 929, 937, 953, 977, 1009, 1129, 1153, 1201, 1217
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

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 p1=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^(rk+1)).
Proof: Choose primitive root g mod p with 2 = g^a mod p, where a=(p1)/ord_p(2). Writing x = g^u, see that solving x^(2^k) = 2 mod p is equivalent to solving 2^k.u + (p1).v = a for some integers u,v.
A necessary and sufficient condition for this is that gcd(2^k,p1)  a. So for p1 = 2^r.j, j odd and ord_p(2) = 2^s.h, h odd, condition becomes min(k,r) <= rs. If s = 0 (ie ord_p(2) odd) this is always valid; for positive s we need k < rs+1, or s < rk+1.


LINKS

Table of n, a(n) for n=1..40.


EXAMPLE

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


MAPLE

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


CROSSREFS

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 * A138005 A267421 A166147
Adjacent sequences: A163182 A163183 A163184 * A163186 A163187 A163188


KEYWORD

easy,nonn


AUTHOR

Christopher J. Smyth, Jul 23 2009


STATUS

approved



