

A366526


Prime powers (A246655) q such that 2 is a nonzero square in the finite field F_q.


3



7, 9, 17, 23, 25, 31, 41, 47, 49, 71, 73, 79, 81, 89, 97, 103, 113, 121, 127, 137, 151, 167, 169, 191, 193, 199, 223, 233, 239, 241, 257, 263, 271, 281, 289, 311, 313, 337, 343, 353, 359, 361, 367, 383, 401, 409, 431, 433, 439, 449, 457, 463, 479, 487, 503, 521, 529
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Prime powers q that are congruent to 1 or 7 modulo 8.
Odd prime powers q such that 2^((q1)/2) = 1 in F_q.
Prime powers q such that x^2  2 splits into different linear factors in F_q[x].
Contains the powers of primes congruent to 1 or 7 modulo 8 and the even powers of primes congruent to 3 or 5 modulo 8.
Proposition 1: Suppose that q is not a power of 2, gcd(a,q) = 1, then a is a square in F_q if and only if the Jacobi symbol Jacobi(a,q) = 1.
Proof: a is a square if and only if a^((q1)/2) == 1 (mod p). We have a^((q1)/2) = (a^((p1)/2))^((q1)/(p1)) == Jacobi(a,p)^((q1)/(p1)) (mod p). Write q = p^e, then by definition, we have Jacobi(a,q) = Jacobi(a,p)^e, so it remains to prove that (q1)/(p1)  e = Sum^{e1}_{i=0} (p^i  1) is always even, which is obvious.
A trivial corollary would be that if q is a square, then every integer a coprime to q is always a square in F_q (since Jacobi(a,q) = 1 in this case). Indeed, since F_q is the unique quadratic extension of F_{sqrt(q)}, every quadratic polynomial with coefficients in F_{sqrt(q)} splits in F_q.
Proposition 2: Suppose that a == 1 (mod 4), gcd(a,q) = 1, then x^2  x  (a1)/4 splits into different linear factors in F_q[x] if and only if Jacobi(q,a) = 1 (or Kronecker(a,q) = 1).
Proof: Proposition 1 deals with the case where q is odd. For even q, we have x^2  x  (a1)/4 = x^2 + x + 1, which is reducible over F_q[x] if and only if q is an even power of 2.


LINKS



EXAMPLE

9 is a term since 2 = 1 = (+i)^2 in F_9 = F_3(i).


PROG

(PARI) isA366526(n) = isprimepower(n) && (n%8==1  n%8==7)


CROSSREFS

Prime powers q such that a is a nonzero square in F_q: A365082 (q=2), A085759 (q=1), this sequence (q=2), A365313 (q=3).


KEYWORD

nonn,easy


AUTHOR



STATUS

approved



