|
%I #12 Aug 27 2022 03:15:34
%S 17,41,73,89,97,113,137,193,233,241,257,313,337,353,401,409,433,449,
%T 457,521,569,577,593,601,641,673,761,769,809,857,881,929,937,953,977,
%U 1009,1129,1153,1201,1217,1249,1289,1297,1321,1361,1409,1433,1489,1601,1609
%N Primes p such that the equation x^2 = -2 mod p has a solution, and ord_p(-2) is even.
%C 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.
%C 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)).
%C 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 u*2^k + v*(p-1) = a for some integers u,v.
%C A necessary and sufficient condition for this is that gcd(2^k,p-1) | a. So for p-1 = j*2^r, j odd and ord_p(-2) = h*2^s, h odd, condition becomes min(k,r) <= r-s. If s = 0 (i.e., ord_p(-2) odd) this is always valid; for positive s we need k < r-s+1, or s < r-k+1.
%H Jinyuan Wang, <a href="/A163185/b163185.txt">Table of n, a(n) for n = 1..1000</a>
%e 17 belongs to this sequence as 7^2 == -2 (mod 17) and ord_p(-2) = 8, even but <> 0 (mod 16).
%p 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;
%o (PARI) lista(nn) = forprime(p=3, nn, if(znorder(Mod(-2, p))%2==0 && []~!=polrootsmod(x^2+2, p), print1(p, ", "))); \\ _Jinyuan Wang_, Mar 24 2020
%Y Cf. A033203 (all p for which x^2 == -2 (mod p) has a solution); .
%Y Cf. A163183 (p with ord_p(-2) odd): a subsequence of A033203, whose complement in A163183 is the current sequence.
%K nonn,easy
%O 1,1
%A _Christopher J. Smyth_, Jul 23 2009
%E More terms from _Jinyuan Wang_, Mar 24 2020
|
