A040028 -id:A040028 - cp's OEIS frontend

A038873 Primes p such that 2 is a square mod p; or, primes congruent to {1, 2, 7} mod 8.

2, 7, 17, 23, 31, 41, 47, 71, 73, 79, 89, 97, 103, 113, 127, 137, 151, 167, 191, 193, 199, 223, 233, 239, 241, 257, 263, 271, 281, 311, 313, 337, 353, 359, 367, 383, 401, 409, 431, 433, 439, 449, 457, 463, 479, 487, 503, 521, 569, 577, 593, 599, 601, 607, 617

Offset: 1

N. J. A. Sloane

Same as A001132 except for initial term.
Primes p such that x^2 = 2 has a solution mod p.
The primes of the form x^2 + 2xy - y^2 coincide with this sequence. These are also primes of the form u^2 - 2v^2. - Tito Piezas III, Dec 28 2008
Therefore these are composite in Z[sqrt(2)], as they can be factored as (u^2 - 2v^2)*(u^2 + 2v^2). - Alonso del Arte, Oct 03 2012
After a(1) = 2, these are the primes p such that p^4 == 1 (mod 96). - Gary Detlefs, Jan 22 2014
Also primes of the form 2v^2 - u^2. For example, 23 = 2*4^2 - 3^2. - Jerzy R Borysowicz, Oct 27 2015
Prime factors of A008865 and A028884. - Klaus Purath, Dec 07 2020

W. J. LeVeque, Topics in Number Theory. Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, Theorem 5-5, p. 68.

Nathaniel Johnston, Table of n, a(n) for n = 1..10000
K. S. Brown, Pythagorean graphs.
N. J. A. Sloane et al., Binary Quadratic Forms and OEIS (Index to related sequences, programs, references)
Index entries for related sequences

Cf. A057126, A087780, A226523, A003629 (complement).
Primes in A035251.
For primes p such that x^m == 2 mod p has a solution for m = 2,3,4,5,6,7,... see A038873, A040028, A040098, A040159, A040992, A042966, ...

[ p: p in PrimesUpTo(617) | IsSquare(R!2) where R:=ResidueClassRing(p) ]; // Klaus Brockhaus, Dec 02 2008

seq(`if`(member(ithprime(n) mod 8, {1,2,7}),ithprime(n),NULL),n=1..113); # Nathaniel Johnston, Jun 26 2011

fQ[n_] := MemberQ[{1, 2, 7}, Mod[n, 8]]; Select[ Prime[Range[114]], fQ] (* Robert G. Wilson v, Oct 18 2011 *)

is(n)=isprime(n) && issquare(Mod(2,n)) \\ Charles R Greathouse IV, Apr 23 2015

is(n)=abs(centerlift(Mod(n,8)))<3 && isprime(n) \\ Charles R Greathouse IV, Nov 14 2017

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

A001132 Primes == +-1 (mod 8).

Original entry on oeis.org

7, 17, 23, 31, 41, 47, 71, 73, 79, 89, 97, 103, 113, 127, 137, 151, 167, 191, 193, 199, 223, 233, 239, 241, 257, 263, 271, 281, 311, 313, 337, 353, 359, 367, 383, 401, 409, 431, 433, 439, 449, 457, 463, 479, 487, 503, 521, 569, 577, 593, 599

Offset: 1

N. J. A. Sloane

Primes p such that 2 is a quadratic residue mod p.
Also primes p such that p divides 2^((p-1)/2) - 1. - Cino Hilliard, Sep 04 2004
A001132 is exactly formed by the prime numbers of A118905: in fact at first every prime p of A118905 is p = u^2 - v^2 + 2uv, with for example u odd and v even so that p - 1 = 4u'(u' + 1) + 4v'(2u' + 1 - v') when u = 2u' + 1 and v = 2v'. u'(u' + 1) is even and v'(2u' + 1 - v') is always even. At second hand if p = 8k +- 1, p has the shape x^2 - 2y^2; letting u = x - y and v = y, comes p = (x - y)^2 - y^2 + 2(x - y)y = u^2 - v^2 + 2uv so p is a sum of the two legs of a Pythagorean triangle. - Richard Choulet, Dec 16 2008
These are also the primes of form x^2 - 2y^2, excluding 2. See A038873. - Tito Piezas III, Dec 28 2008
Primes p such that p^2 mod 48 = 1. - Gary Detlefs, Dec 29 2011
Primes in A047522. - Reinhard Zumkeller, Jan 07 2012
This sequence gives the odd primes p which satisfy C(p, x = 0) = +1, where C(p, x) is the minimal polynomial of 2*cos(Pi/p) (see A187360). For the proof see a comment on C(n, 0) in A230075.  - Wolfdieter Lang, Oct 24 2013
Each a(n) corresponds to precisely one primitive Pythagorean triangle. For a proof see the W. Lang link, also for a table. See also the comment by Richard Choulet above, where the case u even and v odd has not been considered. - Wolfdieter Lang, Feb 17 2015
Primes p such that p^2 mod 16 = 1. - Vincenzo Librandi, May 23 2016
Rational primes that decompose in the field Q(sqrt(2)). - N. J. A. Sloane, Dec 26 2017

Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.
Ronald S. Irving, Integers, Polynomials, and Rings. New York: Springer-Verlag (2004): 274.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Ray Chandler, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
C. Banderier, Calcul de (2/p)
Wolfdieter Lang, A001132: Primes +1 (mod 8) or -1 (mod 8) and Sum of Legs of Primitive Pythagorean Triangles.
Index entries for related sequences
Index to sequences related to decomposition of primes in quadratic fields

For primes p such that x^m = 2 (mod p) has a solution see A001132 (for m = 2), A040028 (m = 3), A040098 (m = 4), A040159 (m = 5), A040992 (m = 6), A042966 (m = 7), A045315 (m = 8), A049596 (m = 9), A049542 (m = 10) - A049595 (m = 63). Jeff Lagarias (lagarias(AT)umich.edu) points out that all these sequences are different, although this may not be apparent from looking just at the initial terms.
Agrees with A038873 except for initial term.
Cf. A118905, A010051.
Union of A007519 and A007522.

a001132 n = a001132_list !! (n-1)
a001132_list = [x | x <- a047522_list, a010051 x == 1]
-- Reinhard Zumkeller, Jan 07 2012

[p: p in PrimesUpTo (600) | p^2 mod 16 eq 1]; // Vincenzo Librandi, May 23 2016

seq(`if`(member(ithprime(n) mod 8, {1,7}),ithprime(n),NULL),n=1..109); # Nathaniel Johnston, Jun 26 2011
for n from 1 to 600 do if (ithprime(n)^2 mod 48 = 1) then print(ithprime(n)) fi od. # Gary Detlefs, Dec 29 2011

Select[Prime[Range[250]], MemberQ[{1, 7}, Mod[#, 8]] &]  (* Harvey P. Dale, Apr 29 2011 *)
Select[Union[8Range[100] - 1, 8Range[100] + 1], PrimeQ] (* Alonso del Arte, May 22 2016 *)

select(p->p%8==1 ||p%8==7, primes(100)) \\ Charles R Greathouse IV, May 18 2015

a(n) ~ 2n log n. - Charles R Greathouse IV, May 18 2015

A040098 Primes p such that x^4 = 2 has a solution mod p.

Original entry on oeis.org

2, 7, 23, 31, 47, 71, 73, 79, 89, 103, 113, 127, 151, 167, 191, 199, 223, 233, 239, 257, 263, 271, 281, 311, 337, 353, 359, 367, 383, 431, 439, 463, 479, 487, 503, 577, 593, 599, 601, 607, 617, 631, 647, 719, 727, 743, 751, 823, 839, 863, 881, 887, 911, 919

Offset: 1

N. J. A. Sloane

For a prime p congruent to 1 mod 8, 2 is a biquadratic residue mod p if and only if there are integers x,y such that x^2 + 64*y^2 = p. 2 is also a biquadratic residue mod 2 and mod p for any prime p congruent to 7 mod 8 and for no other primes. - Fred W. Helenius (fredh(AT)ix.netcom.com), Dec 30 2004

Complement of A040100 relative to A000040. - Vincenzo Librandi, Sep 13 2012

T. D. Noe, Table of n, a(n) for n = 1..1000
Franz Lemmermeyer, Bibliography on Reciprocity Laws
Index entries for related sequences

Cf. A000040, A001132, A040028, A040100, A045315.

For primes p such that x^m == 2 mod p has a solution for m = 2,3,4,5,6,7,... see A038873, A040028, A040098, A040159, A040992, A042966, ...

[ p: p in PrimesUpTo(919) | exists(t){x : x in ResidueClassRing(p) | x^4 eq 2} ]; // Klaus Brockhaus, Dec 02 2008

ok[p_] := Reduce[ Mod[x^4 - 2, p] == 0, x, Integers] =!= False; Select[ Prime[ Range[200]], ok] (* Jean-François Alcover, Dec 14 2011 *)

forprime(p=2,2000,if([]~!=polrootsmod(x^4-2,p),print1(p,", ")));print(); \\ Joerg Arndt, Jul 27 2011

A014752 Primes of the form x^2 + 27y^2.

Original entry on oeis.org

31, 43, 109, 127, 157, 223, 229, 277, 283, 307, 397, 433, 439, 457, 499, 601, 643, 691, 727, 733, 739, 811, 919, 997, 1021, 1051, 1069, 1093, 1327, 1399, 1423, 1459, 1471, 1579, 1597, 1627, 1657, 1699, 1723, 1753, 1777, 1789, 1801, 1831, 1933, 1999, 2017

Offset: 1

Klaus Brockhaus, Mar 02 2001

nonn

Primes p == 1 (mod 3) such that 2 is a cubic residue mod p.
Primes p == 1 (mod 6) such that 2 and -2 are both cubes (one implies the other) mod p. - Warren D. Smith
Subsequence of A040028, complement of A045309 relative to A040028. For p in this sequence, x^3 == 2 (mod p) has three solutions in integers from 0 to p-1, whose sum is p (A059899) or 2*p (A059914). The solutions are given in A060122, A060123 and A060124. - Klaus Brockhaus, Mar 02 2001
Primes p = 3m+1 such that 2^m == 1 (mod p). Subsequence of A016108 which also includes composites satisfying this congruence. - Alzhekeyev Ascar M, Feb 22 2012

K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer, 1982, Prop. 9.6.2, p. 119.

N. J. A. Sloane and T. D. Noe, Table of n, a(n) for n = 1..17753 (The first 1000 terms were computed by T. D. Noe)
Steven R. Finch, Powers of Euler's q-Series, arXiv:math/0701251 [math.NT], 2007.
Bishnu Paudel and Chris Pinner, The integer group determinants for the abelian groups of order 18, arXiv:2412.10638 [math.NT], 2024. See p. 3.
Zak Seidov, Corresponding values of x and y
Bram van Asch, On the structure of the ring Z[2^(1/3)], Internat. J. Pure Appl. Math., 16 (No. 2, 2004), 243-251. See Prop. 7.

Cf. A040028, A045309, A059899, A059914, A060122, A060123, A060124, A014753.

[p: p in PrimesUpTo(2500) | NormEquation(27, p) eq true]; // Vincenzo Librandi, Jul 24 2016

With[{nn=50},Take[Select[Union[First[#]^2+27Last[#]^2&/@Tuples[Range[ nn], 2]],PrimeQ],nn]] (* Harvey P. Dale, Jul 28 2014 *)
nn = 1398781;re = Sort[Reap[Do[Do[If[PrimeQ[p = x^2 + 27*y^2], Sow[{p, x, y}]], {x, Sqrt[nn - 27*y^2]}], {y, Sqrt[nn/27]}]][[2, 1]]]; (* For all 17753 values of a(n), x(n) and y(n). - Zak Seidov, May 20 2016 *)

{ fc(a,b,c,M) = my(p,t1,t2,n); t1 = listcreate();
for(n=1,M, p = prime(n);
t2 = qfbsolve(Qfb(a,b,c),p); if(t2 == 0,, listput(t1,p)));
print(t1);
}
fc(1,0,27,1000);
\\ N. J. A. Sloane, Jun 06 2014

list(lim)=my(v=List()); forprimestep(p=31,lim,6, if(Mod(2,p)^(p\3)==1, listput(v,p))); Vec(v) \\ Charles R Greathouse IV, Apr 06 2022

a(n) ~ 6n log n by the Landau prime ideal theorem. - Charles R Greathouse IV, Apr 06 2022

Definition provided by T. D. Noe, May 08 2005
Entry revised by Michael Somos and N. J. A. Sloane, Jul 28 2006
Defective Mma program replaced with PARI program, b-file recomputed and extended by N. J. A. Sloane, Jun 06 2014

A001133 Primes p such that the multiplicative order of 2 modulo p is (p-1)/3.

Original entry on oeis.org

43, 109, 157, 229, 277, 283, 307, 499, 643, 691, 733, 739, 811, 997, 1021, 1051, 1069, 1093, 1459, 1579, 1597, 1627, 1699, 1723, 1789, 1933, 2179, 2203, 2251, 2341, 2347, 2749, 2917, 3163, 3181, 3229, 3259, 3373, 4027, 4339, 4549, 4597, 4651, 4909, 5101, 5197, 5323, 5413, 5437, 5653, 6037

Offset: 1

N. J. A. Sloane

nonn

M. Kraitchik, Recherches sur la Théorie des Nombres. Gauthiers-Villars, Paris, Vol. 1, 1924, Vol. 2, 1929, see Vol. 1, p. 59.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A040028, A014752, A059914.

Cf. also A001134, A001135, A001136, A115586, A115591.

[ p: p in PrimesUpTo(4597) | r eq 1 and Order(R!2) eq q where q,r is Quotrem(p,3) where R is ResidueClassRing(p) ]; // Klaus Brockhaus, Dec 02 2008

Reap[For[p = 2, p < 10^4, p = NextPrime[p], If[MultiplicativeOrder[2, p] == (p-1)/3, Sow[p]]]][[2, 1]] (* Jean-François Alcover, Dec 10 2015 *)

forprime(p=3,10^4,if(znorder(Mod(2,p))==(p-1)/3,print1(p,", "))); \\ Joerg Arndt, May 17 2013

More terms and better definition from Don Reble, Mar 11 2006

A045309 Primes congruent to {0, 2} mod 3.

Original entry on oeis.org

2, 3, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, 101, 107, 113, 131, 137, 149, 167, 173, 179, 191, 197, 227, 233, 239, 251, 257, 263, 269, 281, 293, 311, 317, 347, 353, 359, 383, 389, 401, 419, 431, 443, 449, 461, 467, 479, 491, 503, 509, 521, 557, 563

Offset: 1

N. J. A. Sloane

Also, primes p such that the equation x^3 == y (mod p) has a unique solution x for every choice of y. - Klaus Brockhaus, Mar 02 2001; Michel Drouzy (DrouzyM(AT)noos.fr), Oct 28 2001

2, 3 and primes congruent to 5 mod 6. - Chai Wah Wu, Apr 28 2025

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

Cf. A040028, A014752, A060121, A003627, A007528, A045410.

[ p: p in PrimesUpTo(1000) | #[ x: x in ResidueClassRing(p) | x^3 eq 2 ] eq 1 ]; // Klaus Brockhaus, Apr 11 2009

Select[Prime[Range[150]],MemberQ[{0,2},Mod[#,3]]&] (* Harvey P. Dale, Jun 14 2011 *)

is(n)=isprime(n) && n%3!=1 \\ Charles R Greathouse IV, Apr 20 2015

from itertools import count, islice
from sympy import isprime
def A045309_gen(): # generator of terms
    yield from (2,3)
    yield from filter(isprime, count(5,6))
A045309_list = list(islice(A045309_gen(),48)) # Chai Wah Wu, Apr 28 2025

a(n) ~ 2n log n. - Charles R Greathouse IV, Apr 20 2015

Edited by N. J. A. Sloane, Apr 11 2009

A040159 Primes p such that x^5 = 2 has a solution mod p.

Original entry on oeis.org

2, 3, 5, 7, 13, 17, 19, 23, 29, 37, 43, 47, 53, 59, 67, 73, 79, 83, 89, 97, 103, 107, 109, 113, 127, 137, 139, 149, 151, 157, 163, 167, 173, 179, 193, 197, 199, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 277, 283, 293, 307, 313, 317, 337, 347, 349, 353

Offset: 1

N. J. A. Sloane

T. D. Noe, Table of n, a(n) for n=1..1000
Index entries for related sequences

Cf. A001132, A040028, A040098, A040160.
Has same beginning as A042991 but is strictly different.
For primes p such that x^m == 2 mod p has a solution for m = 2,3,4,5,6,7,... see A038873, A040028, A040098, A040159, A040992, A042966, ...

[p: p in PrimesUpTo(400) | exists{x: x in ResidueClassRing(p) | x^5 eq 2}]; // Bruno Berselli, Sep 12 2012

ok [p_]:=Reduce[Mod[x^5- 2, p]== 0, x, Integers]=!= False; Select[Prime[Range[180]], ok] (* Vincenzo Librandi, Sep 12 2012 *)

A040992 Primes p such that x^6 = 2 has a solution mod p.

Original entry on oeis.org

2, 17, 23, 31, 41, 47, 71, 89, 113, 127, 137, 167, 191, 223, 233, 239, 257, 263, 281, 311, 353, 359, 383, 401, 431, 433, 439, 449, 457, 479, 503, 521, 569, 593, 599, 601, 617, 641, 647, 719, 727, 743, 761, 809, 839, 857, 863, 881, 887, 911, 919, 929, 953

Offset: 1

N. J. A. Sloane

Complement of A040993 relative to A000040. - Vincenzo Librandi, Sep 13 2012

T. D. Noe, Table of n, a(n) for n = 1..1000
Index entries for related sequences

Cf. A000040, A040993.

For primes p such that x^m == 2 (mod p) has a solution for m = 2,3,4,5,6,7,... see A038873, A040028, A040098, A040159, A040992, A042966, ...

[p: p in PrimesUpTo(1000) | exists(t){x : x in ResidueClassRing(p) | x^6 eq 2}]; // Vincenzo Librandi, Sep 13 2012

ok[p_]:= Reduce[Mod[x^6- 2, p] == 0, x, Integers]=!=False; Select[Prime[Range[200]], ok] (* Vincenzo Librandi, Sep 13 2012 *)

forprime(p=2,2000,if([]~!=polrootsmod(x^6-2,p),print1(p,", ")));print();
/* Joerg Arndt, Jul 27 2011 */

A042966 Primes p such that x^7 = 2 has a solution mod p.

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 41, 47, 53, 59, 61, 67, 73, 79, 83, 89, 97, 101, 103, 107, 109, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 199, 223, 227, 229, 233, 241, 251, 257, 263, 269, 271, 277, 283, 293, 307, 311, 313, 317, 331

Offset: 1

N. J. A. Sloane

Coincides with sequence of "primes p such that x^49 = 2 has a solution mod p" for first 572 terms, then diverges.
Complement of A042967 relative to A000040. - Vincenzo Librandi, Sep 13 2012
a(98) = 631 is the first such prime that is congruent to 1 (mod 7). - Georg Fischer, Jan 06 2022

T. D. Noe, Table of n, a(n) for n = 1..1000
Index entries for related sequences

Cf. A000040, A042967.

For primes p such that x^m == 2 mod p has a solution for m = 2,3,4,5,6,7,... see A038873, A040028, A040098, A040159, A040992, A042966, ...

[p: p in PrimesUpTo(400) | exists{x: x in ResidueClassRing(p) | x^7 eq 2}]; // Bruno Berselli, Sep 12 2012

ok[p_]:= Reduce[Mod[x^7 - 2, p] == 0, x, Integers]=!=False; Select[Prime[Range[100]], ok] (* Vincenzo Librandi, Sep 13 2012 *)

A045315 Primes p such that x^8 = 2 has a solution mod p.

Original entry on oeis.org

2, 7, 23, 31, 47, 71, 73, 79, 89, 103, 127, 151, 167, 191, 199, 223, 233, 239, 257, 263, 271, 311, 337, 359, 367, 383, 431, 439, 463, 479, 487, 503, 599, 601, 607, 631, 647, 719, 727, 743, 751, 823, 839, 863, 881, 887, 911, 919, 937, 967, 983, 991, 1031, 1039

Offset: 1

N. J. A. Sloane

Coincides with the sequence of "primes p such that x^16 = 2 has a solution mod p" for first 58 terms (and then diverges).

Complement of A045316 relative to A000040. - Vincenzo Librandi, Sep 13 2012

A. Aigner, Kriterien zum 8. und 16. Potenzcharakter der Reste 2 und -2, Deutsche Math. 4 (1939), 44-52; FdM 65 - I (1939), 112.

T. D. Noe, Table of n, a(n) for n = 1..1000
H. Hasse, Der 2^n-te Potenzcharakter von 2 im Koerper der 2^n-ten Einheitswurzeln, Rend. Circ. Matem. Palermo (2), 7 (1958), 185-243.
Franz Lemmermeyer, Bibliography on Reciprocity Laws
A. L. Whiteman, The sixteenth power residue character of 2, Canad. J. Math. 6 (1954), 364-373; Zbl 55.27102.
Index entries for related sequences

Cf. A000040, A001132, A040028, A040098, A045316.

[p: p in PrimesUpTo(1100) | exists(t){x : x in ResidueClassRing(p) | x^8 eq 2}]; // Vincenzo Librandi, Sep 13 2012

ok[p_] := Reduce[ Mod[x^8-2, p] == 0, x, Integers] =!= False; Select[ Prime[ Range[200] ], ok] (* Jean-François Alcover, Nov 28 2011 *)

is(n)=isprime(n) && ispower(Mod(2,n),8) \\ Charles R Greathouse IV, Feb 08 2017

cp's OEIS Frontend

A038873 Primes p such that 2 is a square mod p; or, primes congruent to {1, 2, 7} mod 8.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

A001132 Primes == +-1 (mod 8).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Formula

A040098 Primes p such that x^4 = 2 has a solution mod p.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

A014752 Primes of the form x^2 + 27y^2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

Extensions

A001133 Primes p such that the multiplicative order of 2 modulo p is (p-1)/3.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Extensions

A045309 Primes congruent to {0, 2} mod 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI