A045315 -id:A045315 - cp's OEIS frontend

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

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

A014663 Primes p such that multiplicative order of 2 modulo p is odd.

Original entry on oeis.org

7, 23, 31, 47, 71, 73, 79, 89, 103, 127, 151, 167, 191, 199, 223, 233, 239, 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, 1063

Offset: 1

N. J. A. Sloane, Dec 11 1999

nonn

Or, primes p which do not divide 2^n+1 for any n.
The possibility n=0 in the above rules out A072936(1)=2; apart from this, a(n)=A072936(n+1). - M. F. Hasler, Dec 08 2007
The order of 2 mod p is odd iff 2^k=1 mod p, where p-1=2^s*k, k odd. - M. F. Hasler, Dec 08 2007
Has density 7/24 (Hasse).
From Jianing Song, Jun 27 2025: (Start)
The multiplicative order of 2 modulo a(n) is A139686(n).
Contained in primes congruent to 1 or 7 modulo 8 (primes p such that 2 is a quadratic residue modulo p, A001132), and contains primes congruent to 7 modulo 8 (A007522). (End)

Christopher Adler and Jean-Paul Allouche (2022), Finite self-similar sequences, permutation cycles, and music composition, Journal of Mathematics and the Arts, 16:3, 244-261, DOI: 10.1080/17513472.2022.2116745.
P. Moree, Appendix to V. Pless et al., Cyclic Self-Dual Z_4 Codes, Finite Fields Applic., vol. 3 pp. 48-69, 1997.

T. D. Noe, Table of n, a(n) for n=1..1000
H. H. Hasse, Über die Dichte der Primzahlen p, ... , Math. Ann., 168 (1966), 19-23.
J. C. Lagarias, The set of primes dividing the Lucas numbers has density 2/3, Pacific J. Math., 118. No. 2, (1985), 449-461.
Chunlei Li, Nian Li, and Matthew G. Parker, Complementary Sequence Pairs of Types II and III. [From _N. J. A. Sloane_, Jun 16 2012]

Cf. Complement in primes of A091317.
Cf. A001132, A007522, A040098, A045315, A049564, A139686 (the actual multiplicative orders).
Cf. Essentially the same as A072936 (except for missing leading term 2).
Cf. other bases: this sequence (base 2), A385220 (base 3), A385221 (base 4), A385192 (base 5), A163183 (base -2), A385223 (base -3), A385224 (base -4), A385225 (base -5).

okQ[p_] := OddQ[MultiplicativeOrder[2, p]];
Select[Prime[Range[1000]], okQ] (* Jean-François Alcover, Nov 23 2024 *)

isA014663(p)=1==Mod(1,p)<<((p-1)>>factor(p-1,2)[1,2])
listA014663(N=1000)=forprime(p=3,N,isA014663(p)&print1(p", ")) \\ M. F. Hasler, Dec 08 2007

lista(nn) = {forprime(p=3, nn, if (znorder(Mod(2, p)) % 2, print1(p, ", ")););} \\ Michel Marcus, Feb 06 2015

Edited by M. F. Hasler, Dec 08 2007

More terms from Max Alekseyev, Feb 06 2010

A070184 Primes p such that x^8 = 2 has a solution mod p, but x^(8^2) = 2 has no solution mod p.

Original entry on oeis.org

257, 1217, 1249, 1553, 1777, 2113, 2657, 2833, 4049, 4273, 4481, 4993, 5297, 6449, 6481, 6689, 7121, 7489, 8081, 8609, 9137, 9281, 9649, 10177, 10337, 10369, 10433, 11329, 11617, 11633, 12241, 12577, 13121, 13441, 13633, 14321, 14753, 15073, 15121, 15569, 16417, 16433, 16673, 17137

Offset: 1

Klaus Brockhaus, Apr 29 2002

Is this the same as "x^8 = 2 (mod p) has a solution but x^32 = 2 (mod p) doesn't"? It appears that this sequence is exactly the complement of A045316 in A059349. - M. F. Hasler, Jun 21 2024

M. F. Hasler, Table of n, a(n) for n = 1..2000, Jun 22 2024

Cf. A045315, A059667, A070179 - A070183, A070185 - A070188.

[p: p in PrimesUpTo(15000) | not exists{x: x in ResidueClassRing(p) | x^64 eq 2} and exists{x: x in ResidueClassRing(p) | x^8 eq 2}]; // Vincenzo Librandi, Sep 21 2012

ok(p, r, k1, k2)={
    if (  Mod(r,p)^((p-1)/gcd(k1,p-1))!=1, return(0) );
    if (  Mod(r,p)^((p-1)/gcd(k2,p-1))==1, return(0) );
    return(1);
}
forprime(p=2,10^5, if (ok(p,2,8,8^2),print1(p,", ")));
/* Joerg Arndt, Sep 21 2012 */

select( {is_A070184(p)=Mod(2,p)^(p\gcd(8,p-1))==1 && Mod(2,p)^(p\gcd(64,p-1))!=1 && isprime(p)}, primes(1999)) \\ The only composite numbers that would pass the test without isprime are A242880. - M. F. Hasler, Jun 22 2024

from itertools import islice
from sympy import is_nthpow_residue, nextprime
def A070184_gen(startvalue=2): # generator of terms >= startvalue
    p = max(1,startvalue-1)
    while (p:=nextprime(p)):
        if is_nthpow_residue(2,8,p) and not is_nthpow_residue(2,64,p):
            yield p
A070184_list = list(islice(A070184_gen(),10)) # Chai Wah Wu, Jun 23 2024

A045316 Primes p such that x^8 = 2 has no solution mod p.

Original entry on oeis.org

3, 5, 11, 13, 17, 19, 29, 37, 41, 43, 53, 59, 61, 67, 83, 97, 101, 107, 109, 113, 131, 137, 139, 149, 157, 163, 173, 179, 181, 193, 197, 211, 227, 229, 241, 251, 269, 277, 281, 283, 293, 307, 313, 317, 331, 347, 349, 353, 373, 379, 389

Offset: 1

N. J. A. Sloane

Complement of A045315 relative to A000040. Coincides for the first 140 terms with the sequence of primes p such that x^16 = 2 has no solution mod p (first divergence is at 1217, cf. A059287). - Klaus Brockhaus, Jan 26 2001

Differs from A059349 (x^32 == 2 (mod p) has no solution) first at a(37) = A059349(38), the term A059349(37) = 257 which is not in this sequence. See A070184 for all such terms. - M. F. Hasler, Jun 21 2024

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

Cf. A000040, A045315 (complement in the primes), A059287.

Subsequence of A059349 (same with x^32), complement is A070184.

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

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

select( {is_A045316(p)=Mod(2,p)^(p\gcd(8,p-1))!=1 && p>2}, primes(199)) \\ Append "&& isprime(p)" if that's not known. - M. F. Hasler, Jun 22 2024

A059287 Primes p such that x^16 = 2 has no solution mod p, but x^8 = 2 has a solution mod p.

Original entry on oeis.org

1217, 1249, 1553, 1777, 2833, 4049, 4273, 4481, 4993, 5297, 6449, 6481, 6689, 7121, 8081, 8609, 9137, 9281, 9649, 10337, 10369, 10433, 11329, 11617, 11633, 12241, 12577, 13121, 13441, 13633, 14321, 14753, 15121, 15569, 16417, 16433, 16673

Offset: 1

Klaus Brockhaus, Jan 25 2001

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

Cf. A000040, A045315, A045316.

Cf. A070184 (same with x^64 instead of x^16).

[p: p in PrimesUpTo(17000) | not exists{x: x in ResidueClassRing(p) | x^16 eq 2} and exists{x: x in ResidueClassRing(p) | x^8 eq 2}]; // Vincenzo Librandi, Sep 21 2012

Select[Prime[Range[PrimePi[20000]]], !MemberQ[PowerMod[Range[#], 16, #], Mod[2, #]] && MemberQ[PowerMod[Range[#], 8, #], Mod[2, #]]&] (* Vincenzo Librandi, Sep 21 2013 *)

select( {is_A059287(p)=Mod(2,p)^(p\gcd(8,p-1))==1&&Mod(2,p)^(p\gcd(16,p-1))!=1}, primes(1999)) \\ Could any composite number pass this test? - M. F. Hasler, Jun 22 2024

from itertools import islice
from sympy import is_nthpow_residue, nextprime
def A059287_gen(startvalue=2): # generator of terms >= startvalue
    p = max(1,startvalue-1)
    while (p:=nextprime(p)):
        if is_nthpow_residue(2,8,p) and not is_nthpow_residue(2,16,p):
            yield p
A059287_list = list(islice(A059287_gen(),10)) # Chai Wah Wu, Jun 23 2024

A070181 Primes p such that x^4 = 2 has a solution mod p, but x^(4^2) = 2 has no solution mod p.

Original entry on oeis.org

113, 281, 353, 577, 593, 617, 1033, 1049, 1097, 1153, 1193, 1201, 1217, 1249, 1481, 1553, 1601, 1753, 1777, 1889, 2129, 2273, 2281, 2393, 2473, 2689, 2833, 2857, 3049, 3089, 3121, 3137, 3217, 3313, 3361, 3529, 3673, 3761, 3833, 4001, 4049, 4153, 4217

Offset: 1

Klaus Brockhaus, Apr 29 2002

Cf. A040098, A045315, A045316, A059667, A070179, A070180, A070182 - A070188.

[p: p in PrimesUpTo(5000) | not exists{x: x in ResidueClassRing(p) | x^16 eq 2} and exists{x: x in ResidueClassRing(p) | x^4 eq 2}]; // Vincenzo Librandi, Sep 21 2012

PARI
```
forprime(p=2,4250,x=0; while(x
				
```

ok(p, r, k1, k2)={
    if (  Mod(r,p)^((p-1)/gcd(k1,p-1))!=1, return(0) );
    if (  Mod(r,p)^((p-1)/gcd(k2,p-1))==1, return(0) );
    return(1);
}
forprime(p=2,10^5, if (ok(p,2,4,4^2),print1(p,", ")));
/* Joerg Arndt, Sep 21 2012 */

A252279 Primes p congruent to 1 mod 16 such that x^8 = 2 has a solution mod p.

Original entry on oeis.org

257, 337, 881, 1217, 1249, 1553, 1777, 2113, 2593, 2657, 2833, 4049, 4177, 4273, 4481, 4513, 4721, 4993, 5297, 6353, 6449, 6481, 6529, 6689, 7121, 7489, 8081, 8609, 9137, 9281, 9649, 10177, 10337, 10369, 10433, 10657, 11329, 11617, 11633, 12049, 12241, 12577

Offset: 1

Arkadiusz Wesolowski, Dec 16 2014

nonn

For a prime p congruent to 1 mod 16, the number 2 is an octavic residue mod p if and only if there are integers x and y such that x^2 + 256*y^2 = p.

Arkadiusz Wesolowski, Table of n, a(n) for n = 1..10000
Index entries for related sequences

Subsequence of A045315.

Has A070184 as a subsequence.

[p: p in PrimesUpTo(12577) | p mod 16 eq 1 and exists(t){x : x in ResidueClassRing(p) | x^8 eq 2}]; // Arkadiusz Wesolowski, Dec 19 2020

isok(p) = isprime(p) && (Mod(p, 16) == 1) && ispower(Mod(2, p), 8); \\ Michel Marcus, Dec 19 2020

cp's OEIS Frontend

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

A014663 Primes p such that multiplicative order of 2 modulo p is odd.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

A070184 Primes p such that x^8 = 2 has a solution mod p, but x^(8^2) = 2 has no solution mod p.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

PARI

PARI

Python

A045316 Primes p such that x^8 = 2 has no solution mod p.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

A059287 Primes p such that x^16 = 2 has no solution mod p, but x^8 = 2 has a solution mod p.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

A070181 Primes p such that x^4 = 2 has a solution mod p, but x^(4^2) = 2 has no solution mod p.

Views

Author

Keywords

Crossrefs

Programs