A033203 -id:A033203 - cp's OEIS frontend

A033200 Primes congruent to {1, 3} (mod 8); or, odd primes of form x^2 + 2*y^2.

3, 11, 17, 19, 41, 43, 59, 67, 73, 83, 89, 97, 107, 113, 131, 137, 139, 163, 179, 193, 211, 227, 233, 241, 251, 257, 281, 283, 307, 313, 331, 337, 347, 353, 379, 401, 409, 419, 433, 443, 449, 457, 467, 491, 499

Offset: 1

N. J. A. Sloane

Rational primes that decompose in the field Q(sqrt(-2)). - N. J. A. Sloane, Dec 25 2017
Fermat knew of the relationship between a prime being congruent to 1 or 3 mod 8 and its being the sum of a square and twice a square, and claimed to have a firm proof of this fact. These numbers are not primes in Z[sqrt(-2)], as they have x - y sqrt(-2) as a divisor. - Alonso del Arte, Dec 07 2012
Terms m in A047471 with A010051(m) = 1. - Reinhard Zumkeller, Dec 29 2012
This sequence gives the primes p which satisfy norm(rho(p)) = + 1 with rho(p) := 2*cos(Pi/p) (the length ratio (smallest diagonal)/side in the regular p-gon). The norm of an algebraic number (over Q) is the product over all zeros of its minimal polynomial. Here norm(rho(p)) = (-1)^delta(p)* C(p, 0), with the degree delta(p) = A055034(p) = (p-1)/2. For the minimal polynomial C see A187360. For p == 1 (mod 8) the norm is C(p, 0) (see a comment on 4*A005123) and for p == 3 (mod 8) the norm is -C(p, 0) (see a comment on A186297). For the primes with norm(rho(p)) = -1 see A003628. - Wolfdieter Lang, Oct 24 2013
If p is a member then it has a unique representation as x^2+2y^2 [Frei, Theorem 3]. - N. J. A. Sloane, May 30 2014
Primes that are the quarter perimeter of a Heronian triangle. Such primes are unique to the Heronian triangle (see Yiu link). - Frank M Jackson, Nov 30 2014

			Since 11 is prime and 11 == 3 (mod 8), 11 is in the sequence. (Also 11 = 3^2 + 2 * 1^2 = (3 + sqrt(-2))(3 - sqrt(-2)).)
Since 17 is prime and 17 == 1 (mod 8), 17 is in the sequence.

David A. Cox, "Primes of the Form x^2 + n y^2", Wiley, 1989, p. 7.

Ray Chandler, Table of n, a(n) for n = 1..10000 [First 1000 terms from T. D. Noe]
G. Frei, Euler's convenient numbers, Math. Intell. Vol. 7 No. 3 (1985), p. 56.
Zak Seidov, Table of n, a(n), x and y for n = 1..1000
N. J. A. Sloane et al., Binary Quadratic Forms and OEIS (Index to related sequences, programs, references)
Paul Yiu, CRUX, Problem 2331, Proposed by Paul Yiu
Paul Yiu and Jill S. Taylor, CRUX, Problem 2331, Solution pp 185-186
Index to sequences related to decomposition of primes in quadratic fields

Cf. A033203.

a033200 n = a033200_list !! (n-1)
a033200_list = filter ((== 1) . a010051) a047471_list
-- Reinhard Zumkeller, Dec 29 2012

[p: p in PrimesUpTo(600) | p mod 8 in [1, 3]]; // Vincenzo Librandi, Aug 04 2012

Rest[QuadPrimes2[1, 0, 2, 10000]] (* see A106856 *)
Select[Prime[Range[200]],MemberQ[{1,3},Mod[#,8]]&] (* Harvey P. Dale, Jun 09 2017 *)

is(n)=n%8<4 && n%2 && isprime(n) \\ Charles R Greathouse IV, Feb 09 2017

a(n) = A033203(n+1). - Zak Seidov, May 29 2014
A007519 UNION A007520. - R. J. Mathar, Jun 09 2020
L(-2, a(n)) = +1, n >= 1, with the Legendre symbol L. -Wolfdieter Lang, Jul 24 2024

A163183 Primes dividing 2^j + 1 for some odd j.

Original entry on oeis.org

3, 11, 19, 43, 59, 67, 83, 107, 131, 139, 163, 179, 211, 227, 251, 281, 283, 307, 331, 347, 379, 419, 443, 467, 491, 499, 523, 547, 563, 571, 587, 617, 619, 643, 659, 683, 691, 739, 787, 811, 827, 859, 883, 907, 947, 971, 1019, 1033, 1049, 1051, 1091, 1097

Offset: 1

Christopher J. Smyth, Jul 22 2009

Also the primes p for which ord_p(-2) is odd, as (-2)^j == 1 (mod p).
All such p are = 1 or 3 mod 8, so sequence is subsequence of A033200, as (-2)^{j+1} == -2 (mod p) implies that (-2/p) = 1, p == 1 or 3 (mod 8).
Claim: Sequence contains all primes = 3 mod 8, so contains A007520 as a subsequence.
Proof: If p = 8r + 3 then 2^{4r+1} == 1 or -1 (mod p). If former, then (2^{2r+1})^2 == 2 (mod p), (2/p) = 1, only true for p == 1 or 7 (mod 8). So p | 2^{4r+1} + 1.
Also contains some primes == 1 (mod 8), given in A163184. So sequence is a union of A007520 and A163184.
Claim: For every p in sequence and every 2^k, the equation x^{2^k} == -2 (mod p) is soluble. Hence sequence is a subsequence of A033203 (k=1), A051071 (k=2), A051073 (k=3), A051077 (k=4), A051085 (k=5), A051101 (k=6), ....
Proof: Put x == (-2)^u (mod p). Then using (-2)^j == 1 (mod p), we can solve x^{2^k} == -2 (mod p) if can find u and v such that u*2^k + v*j = 1, possible as gcd(2^k, j) = 1.
From Jianing Song, Jun 22 2025: (Start)
The multiplicative order of -2 modulo a(n) is A385228(n).
Contained in primes congruent to 1 or 3 modulo 8 (primes p such that -2 is a quadratic residue modulo p, A033200), and contains primes congruent to 3 modulo 8 (A007520).
Conjecture: this sequence has density 7/24 among the primes (see A014663). (End)

			11 is in sequence as 11 | 2^5 + 1; 281 (smallest element of the sequence == 1 (mod 8)) is in the sequence as 281 | 2^35 + 1.

Jianing Song, Table of n, a(n) for n = 1..10000

Sequence is a union of A007520 and A163184.
Subsequence of A033200. Contains A007520 as a subsequence.
Cf. A385228 (the actual multiplicative orders).
Cf. other bases: A014663 (base 2), A385220 (base 3), A385221 (base 4), A385192 (base 5), this sequence (base -2), A385223 (base -3), A385224 (base -4), A385225 (base -5).

with(numtheory):A:=3:p:=3: for c to 500 do p:=nextprime(p);if order(-2,p) mod 2=1 then A:=A,p;;fi;od:A;

Select[Prime[Range[200]], OddQ[MultiplicativeOrder[-2, #]] &] (* Paolo Xausa, Jun 30 2025 *)

lista(nn) = forprime(p=3, nn, if(znorder(Mod(-2, p))%2, print1(p, ", "))); \\ Jinyuan Wang, Mar 23 2020

A045331 Primes congruent to {1, 2, 3} mod 6; or, -3 is a square mod p.

Original entry on oeis.org

2, 3, 7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97, 103, 109, 127, 139, 151, 157, 163, 181, 193, 199, 211, 223, 229, 241, 271, 277, 283, 307, 313, 331, 337, 349, 367, 373, 379, 397, 409, 421, 433, 439, 457, 463, 487, 499, 523, 541, 547, 571, 577, 601, 607, 613

Offset: 1

N. J. A. Sloane

-3 is a quadratic residue mod a prime p iff p is in this sequence.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Apart from initial term, same as A007645; apart from initial two terms, same as A002476.
Cf. A002313, A033203, A038873, A038874, A057128.
Subsequence of A047246.

a045331 n = a045331_list !! (n-1)
a045331_list = filter ((< 4) . (`mod` 6)) a000040_list
-- Reinhard Zumkeller, Jan 15 2013

[p: p in PrimesUpTo(700) | p mod 6 in [1, 2, 3]]; // Vincenzo Librandi, Aug 08 2012

Select[Prime[Range[200]],MemberQ[{1,2,3},Mod[#,6]]&]  (* Harvey P. Dale, Mar 31 2011 *)
Join[{2,3},Select[Range[7,10^3,6],PrimeQ]] (* Zak Seidov, May 20 2011 *)

select(n->n%6<5,primes(100)) \\ Charles R Greathouse IV, May 20 2011

More terms from Henry Bottomley, Aug 10 2000

A057127 -2 is a square mod n.

Original entry on oeis.org

1, 2, 3, 6, 9, 11, 17, 18, 19, 22, 27, 33, 34, 38, 41, 43, 51, 54, 57, 59, 66, 67, 73, 81, 82, 83, 86, 89, 97, 99, 102, 107, 113, 114, 118, 121, 123, 129, 131, 134, 137, 139, 146, 153, 162, 163, 166, 171, 177, 178, 179, 187, 193, 194, 198, 201, 209, 211, 214, 219

Offset: 1

Henry Bottomley, Aug 10 2000

nonn

Includes the primes in A033203 and these (primes congruent to {1, 2, 3} mod 8) are the prime factors of the terms in this sequence.
Numbers that are not multiples of 4 and for which all odd prime factors are congruent to {1, 3} mod 8. - Eric M. Schmidt, Apr 21 2013
Positive integers primitively represented by x^2 + 2y^2. - Ray Chandler, Jul 22 2014
The set of the divisors of numbers of the form k^2+2. - Michel Lagneau, Jun 28 2015
The number of proper solutions (x, y) with nonnegative x of the positive definite primitive quadratic form x^2 + 2*y*2 (discriminant -8) representing a(n) is 1 for n = 1 and for n >= 2 it is 2^(P_1 + P_3), where P_1 and P_3 are the number of distinct prime divisors of a(n) congruent to 1 and 3 modulo 8, respectively. See the above comments on A033203 and this binary form. - Wolfdieter Lang, Feb 25 2021

			Binary quadratic form x^2 + 2*y^2 representing a(n), with x >= 0: a(1) = 1: one solution (x, y) = (1,0); a(2) = 2: one solution (0,1); a(3) = 3: two solutions (1, pm 1), with pm = +1 or -1; a(5) = 9 = 3^2: two solutions (1, pm 2); a(12) = 33 = 3*11: 4 solutions (1, pm 4) and (5, pm 2); a(137) = 3*11*17 = 561: eight solutions (7, pm 16), (13, pm 14), (19, pm 10) and (23, pm 4). - _Wolfdieter Lang_, Feb 25 2021

Eric M. Schmidt, Table of n, a(n) for n = 1..1000
N. J. A. Sloane et al., Binary Quadratic Forms and OEIS (Index to related sequences, programs, references)

Cf. A008784, A033203, A057125, A057126, A057128, A057129.

select(n -> numtheory:-msqrt(-2,n) <> FAIL, [$1..1000]); # Robert Israel, Jun 29 2015

Select[Range[300], IntegerQ[PowerMod[-2, 1/2, #]]&] // Quiet (* Jean-François Alcover, Mar 04 2019 *)

isok(n) = issquare(Mod(-2, n)); \\ Michel Marcus, Jun 28 2015

def isA057127(n):
    if n % 4 == 0: return False
    return all(p % 8 in [1, 2, 3] for p, _ in factor(n))
[n for n in range(1, 300) if isA057127(n)]
# Eric M. Schmidt, Apr 21 2013

A038874 Primes p such that 3 is a square mod p.

Original entry on oeis.org

2, 3, 11, 13, 23, 37, 47, 59, 61, 71, 73, 83, 97, 107, 109, 131, 157, 167, 179, 181, 191, 193, 227, 229, 239, 241, 251, 263, 277, 311, 313, 337, 347, 349, 359, 373, 383, 397, 409, 419, 421, 431, 433, 443, 457, 467, 479, 491, 503, 541, 563, 577, 587, 599, 601

Offset: 1

N. J. A. Sloane

Also primes congruent to {1, 2, 3, 11} mod 12.
The subsequence p = 1 (mod 4) corresponds to A068228 and only these entries of a(n) are squares mod 3 (from the quadratic reciprocity law). - Lekraj Beedassy, Jul 21 2004
Largest prime factors of n^2 - 3. - Vladimir Joseph Stephan Orlovsky, Aug 12 2009
Aside from 2 and 3, primes p such that Legendre(3, p) = 1. Bolker asserts there are infinitely many of these primes. - Alonso del Arte, Nov 25 2015
The associated bases of the squares are 1, 0, 5, 4, 7, 15, 12, 11, 8, 28, 21, 13...: 1^2 = 3 -1*2, 0^2 = 3-1*3, 5^2 = 3+ 2*11, 4^2 = 3+1*13, 7^2 = 3+2*23, 15^2 = 3+6*37, 12^2 = 3+3*47,... - R. J. Mathar, Feb 23 2017

			11 is in the sequence since the equation x^2 - 11y = 3 has solutions, such as x = 5, y = 2.
13 is in the sequence since the equation x^2 - 13y = 3 has solutions, such as x = 4, y = 1.
17 is not in the sequence because x^2 - 17y = 3 has no solutions in integers; Legendre(3, 17) = -1.

Ethan D. Bolker, Elementary Number Theory: An Algebraic Approach. Mineola, New York: Dover Publications (1969, reprinted 2007): p. 74, Theorem 25.3.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Tamara M. Lavshuk, Regular polygons and polyhedra over finite field, Mathematical Notes of NEFU, Vol 22 No 4 (2015). Mentions this sequence.

Cf. A002313, A033203, A038873, A045331, A057125.

If the first two terms are omitted we get A097933. A040101 is another sequence.

[p: p in PrimesUpTo(1200) | p mod 12 in [1, 2, 3, 11]]; // Vincenzo Librandi, Aug 08 2012

select(isprime, [2,3, seq(seq(6+s+12*i, s=[-5,5]),i=0..1000)]); # Robert Israel, Dec 23 2015

Select[Prime[Range[250]], MemberQ[{1, 2, 3, 11}, Mod[#, 12]] &] (* Vincenzo Librandi, Aug 08 2012 *)
Select[Flatten[Join[{2, 3}, Table[{12n - 1, 12n + 1}, {n, 50}]]], PrimeQ] (* Alonso del Arte, Nov 25 2015 *)

forprime(p=2, 1e3, if(issquare(Mod(3, p)), print1(p , ", "))) \\ Altug Alkan, Dec 04 2015

a(n) ~ 2n log n. - Charles R Greathouse IV, Nov 29 2016

More terms from Henry Bottomley, Aug 10 2000

A341784 Norms of prime elements in Z[sqrt(-2)], the ring of integers of Q(sqrt(-2)).

Original entry on oeis.org

2, 3, 11, 17, 19, 25, 41, 43, 49, 59, 67, 73, 83, 89, 97, 107, 113, 131, 137, 139, 163, 169, 179, 193, 211, 227, 233, 241, 251, 257, 281, 283, 307, 313, 331, 337, 347, 353, 379, 401, 409, 419, 433, 443, 449, 457, 467, 491, 499, 521, 523, 529, 547, 563

Offset: 1

Jianing Song, Feb 19 2021

Also norms of prime ideals in Z[sqrt(-2)], which is a unique factorization domain. The norm of a nonzero ideal I in a ring R is defined as the size of the quotient ring R/I.
Consists of the primes congruent to 1, 2, 3 modulo 8 and the squares of primes congruent to 5, 7 modulo 8.
For primes p == 1, 3 (mod 8), there are two distinct ideals with norm p in Z[sqrt(2)], namely (x + y*sqrt(-2)) and (x - y*sqrt(-2)), where (x,y) is a solution to x^2 + 2*y^2 = p; for p = 2, (sqrt(-2)) is the unique ideal with norm p; for p == 5, 7 (mod 8), (p) is the only ideal with norm p^2.

			norm(1 + sqrt(-2)) = norm(1 + sqrt(-2)) = 3;
norm(3 + sqrt(-2)) = norm(3 + sqrt(-2)) = 11;
norm(3 + 2*sqrt(-2)) = norm(3 + 2*sqrt(-2)) = 17;
norm(1 + 3*sqrt(-2)) = norm(1 + 3*sqrt(-2)) = 19.

Jianing Song, Table of n, a(n) for n = 1..10000

Cf. A188510, A033203, A033200, A003628.
The number of nonassociative elements with norm n (also the number of distinct ideals with norm n) is given by A002325.
The total number of elements with norm n is given by A033715.
Norms of prime ideals in O_K, where K is the quadratic field with discriminant D and O_K be the ring of integers of K: A055673 (D=8), A341783 (D=5), A055664 (D=-3), A055025 (D=-4), A090348 (D=-7), this sequence (D=-8), A341785 (D=-11), A341786 (D=-15*), A341787 (D=-19), A091727 (D=-20*), A341788 (D=-43), A341789 (D=-67), A341790 (D=-163). Here a "*" indicates the cases where O_K is not a unique factorization domain.

isA341784(n) = my(disc=-8); (isprime(n) && kronecker(disc,n)>=0) || (issquare(n, &n) && isprime(n) && kronecker(disc,n)==-1)

A141170 Primes of the form x^2+4xy-2y^2 (as well as of the form 3x^2+6xy+y^2).

Original entry on oeis.org

3, 19, 43, 67, 73, 97, 139, 163, 193, 211, 241, 283, 307, 313, 331, 337, 379, 409, 433, 457, 499, 523, 547, 571, 577, 601, 619, 643, 673, 691, 739, 769, 787, 811, 859, 883, 907, 937, 1009, 1033, 1051, 1123, 1129, 1153, 1171, 1201, 1249, 1291, 1297, 1321, 1459, 1483, 1489, 1531

Offset: 1

Laura Caballero Fernandez, Lourdes Calvo Moguer, Maria Josefa Cano Marquez, Oscar Jesus Falcon Ganfornina and Sergio Garrido Morales (oscfalgan(AT)yahoo.es), Jun 12 2008

nonn

Discriminant = 24. Class = 2. Binary quadratic forms a*x^2 + b*x*y + c*y^2 have discriminant d = b^2 - 4ac.
Also, primes of form u^2 - 6v^2. The transformation {u,v} = {x+2y,y} yields the form in the title. - Tito Piezas III, Dec 31 2008
Conjecture: this is also the list of primes that are simultaneously of the form x^2+2y^2 and of the form x^2+3y^2; that is, the intersection of A002476 and A033203. - Zak Seidov, Jun 07 2014
This is also the list of primes p such that p = 3 or p is congruent to 1 or 19 mod 24. - Jean-François Alcover, Oct 28 2016

			a(2)=19 because we can write 19=3^2+4*3*1-2*1^2 (or 19=3*1^2+6*1*2+2^2)

Z. I. Borevich and I. R. Shafarevich, Number Theory.

Juan Arias-de-Reyna, Table of n, a(n) for n = 1..10000
N. J. A. Sloane et al., Binary Quadratic Forms and OEIS: Index to related sequences, programs, references. OEIS wiki, June 2014.
D. B. Zagier, Zetafunktionen und quadratische Körper, Springer, 1981.

Cf. A141171 (d=24), A106950 (Primes of the form x^2+18y^2), A038872 (d=5). A038873 (d=8). A068228, A141123 (d=12). A038883 (d=13). A038889 (d=17). A141111, A141112 (d=65).
Cf. also A242661, A002476, A033203.
For a list of sequences giving numbers and/or primes represented by binary quadratic forms, see the "Binary Quadratic Forms and OEIS" link.

xy[{x_, y_}]:={x^2 + 4 x y - 2 y^2, y^2 + 4 x y - 2 x^2}; Union[Select[Flatten[xy/@Subsets[Range[40], {2}]], #>0&&PrimeQ[#]&]] (* Vincenzo Librandi, Jun 09 2014 *)
Select[Prime[Range[250]], # == 3 || MatchQ[Mod[#, 24], 1|19]&] (* Jean-François Alcover, Oct 28 2016 *)

A047476 Numbers that are congruent to {0, 1, 2, 3} mod 8.

Original entry on oeis.org

0, 1, 2, 3, 8, 9, 10, 11, 16, 17, 18, 19, 24, 25, 26, 27, 32, 33, 34, 35, 40, 41, 42, 43, 48, 49, 50, 51, 56, 57, 58, 59, 64, 65, 66, 67, 72, 73, 74, 75, 80, 81, 82, 83, 88, 89, 90, 91, 96, 97, 98, 99, 104, 105, 106, 107, 112, 113, 114, 115, 120, 121, 122

Offset: 1

N. J. A. Sloane

Primes of this sequence are in A033203. All of these numbers satisfy the condition that n XOR 4 = n + 4. - Brad Clardy, Jul 24 2012

Numbers k such that floor(k/4) = 2*floor(k/8). - Bruno Berselli, Oct 05 2017

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (1,0,0,1,-1).

Cf. A033203 (primes), A047467, A047471.

a047476 n = a047476_list !! (n-1)
a047476_list = [n | n <- [1..], mod n 8 <= 3]
-- Reinhard Zumkeller, Dec 29 2012

I:=[0, 1, 2, 3, 8]; [n le 5 select I[n] else Self(n-1)+Self(n-4)-Self(n-5): n in [1..70]]; // Vincenzo Librandi, May 16 2012

A047476:=n->(-7-(-1)^n-(1-I)*(-I)^n-(1+I)*I^n+4*n)/2: seq(A047476(n), n=1..100); # Wesley Ivan Hurt, Jun 01 2016

Select[Range[0,300], MemberQ[{0,1,2,3}, Mod[#,8]]&] (* Vincenzo Librandi, May 16 2012 *)
LinearRecurrence[{1,0,0,1,-1},{0,1,2,3,8},100] (* G. C. Greubel, Jun 01 2016 *)

x='x+O('x^100); concat(0, Vec(x^2*(1+x+x^2+5*x^3)/((1-x)^2*(1+x)*(1+x^2)))) \\ Altug Alkan, Dec 24 2015

a(n) = 8 * floor(n/4) + (n mod 4), with offset 0.. a(0)=0. - Gary Detlefs, Mar 09 2010
From Colin Barker, May 14 2012: (Start)
a(n) = (-7 - (-1)^n - (1-i)*(-i)^n - (1+i)*i^n + 4*n)/2, where i=sqrt(-1).
G.f.: x^2*(1 + x + x^2 + 5*x^3)/((1 - x)^2*(1 + x)*(1 + x^2)). (End)
a(n) = a(n-1) + a(n-4) - a(n-5). - Vincenzo Librandi, May 16 2012
a(2*k) = A047471, a(2*k-1) = A047467(k). - Wesley Ivan Hurt, Jun 01 2016
E.g.f.: 5 + sin(x) - cos(x) + (2*x - 3)*sinh(x) + 2*(x - 2)*cosh(x). - Ilya Gutkovskiy, Jun 01 2016
Sum_{n>=2} (-1)^n/a(n) = (2*sqrt(2)-1)*Pi/16 + 5*log(2)/8. - Amiram Eldar, Dec 19 2021

A051100 Primes p such that x^62 = -2 has a solution mod p.

Original entry on oeis.org

2, 3, 11, 17, 19, 41, 43, 59, 67, 73, 83, 89, 97, 107, 113, 131, 137, 139, 163, 179, 193, 211, 227, 233, 241, 251, 257, 281, 283, 307, 313, 331, 337, 347, 353, 379, 401, 409, 419, 433, 443, 449, 457, 467, 491, 499, 521, 523, 547, 563, 569, 571, 577, 587, 593, 601, 617, 619, 641, 643, 659, 673, 683, 691, 739, 761, 769, 787, 809, 811, 827, 857, 859, 881, 883, 907, 929, 937, 947, 953, 971, 977, 1009

Offset: 1

N. J. A. Sloane

Differs from A033203 first at the 109th entry, at p=1427. - R. J. Mathar, Oct 14 2008

Complement of A216776 relative to A000040. - Vincenzo Librandi, Sep 17 2012

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

[p: p in PrimesUpTo(1010) | exists(t){x : x in ResidueClassRing(p) | x^62 eq - 2}]; // Vincenzo Librandi, Sep 16 2012

ok[p_]:= Reduce[Mod[x^62 + 2, p] == 0, x, Integers] =!= False; Select[Prime[Range[500]], ok] (* Vincenzo Librandi, Sep 16 2012 *)

PARI
```
/* see A051071 */
```

More terms from Joerg Arndt, Jul 27 2011

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

Original entry on oeis.org

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, 1249, 1289, 1297, 1321, 1361, 1409, 1433, 1489, 1601, 1609

Offset: 1

Christopher J. Smyth, Jul 23 2009

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 u*2^k + v*(p-1) = 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 = 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.

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

Jinyuan Wang, Table of n, a(n) for n = 1..1000

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.

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;

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

More terms from Jinyuan Wang, Mar 24 2020

cp's OEIS Frontend

A033200 Primes congruent to {1, 3} (mod 8); or, odd primes of form x^2 + 2*y^2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Formula

A163183 Primes dividing 2^j + 1 for some odd j.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A045331 Primes congruent to {1, 2, 3} mod 6; or, -3 is a square mod p.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Extensions

A057127 -2 is a square mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

A038874 Primes p such that 3 is a square mod p.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A341784 Norms of prime elements in Z[sqrt(-2)], the ring of integers of Q(sqrt(-2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A141170 Primes of the form x^2+4xy-2y^2 (as well as of the form 3x^2+6xy+y^2).