A003629 Primes p == +- 3 (mod 8), or, primes p such that 2 is not a square mod p.

3, 5, 11, 13, 19, 29, 37, 43, 53, 59, 61, 67, 83, 101, 107, 109, 131, 139, 149, 157, 163, 173, 179, 181, 197, 211, 227, 229, 251, 269, 277, 283, 293, 307, 317, 331, 347, 349, 373, 379, 389, 397, 419, 421, 443, 461, 467, 491, 499, 509, 523, 541, 547, 557, 563

Offset: 1

Author

N. J. A. Sloane, Mira Bernstein

Keywords

• nonn
• easy

Comments

Complement of A038873 relative to A000040.

Also primes p such that p divides 2^((p-1)/2) + 1. - Cino Hilliard, Sep 04 2004

Primes p such that p^2 == 25 (mod 48), n > 1. - Gary Detlefs, Dec 29 2011

This sequence gives the 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 a proof see a comment on C(n, 0) in A230075. - Wolfdieter Lang, Oct 24 2013

Except for the initial 3, these are the primes p such that Fibonacci(p) mod 6 = 5. - Gary Detlefs, May 26 2014

Inert rational primes in the field Q(sqrt(2)). - N. J. A. Sloane, Dec 26 2017

If a prime p is congruent to 3 or 5 (mod 8) and r > 1, then 2^((p-1)*p^(r-1)/2) == -1 (mod p^r). - Marina Ibrishimova, Sep 29 2018

For the proofs or the comments by Cino Hilliard and Marina Ibrishimova, see link below. - Robert Israel, Apr 24 2019

References

• 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 and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• 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].
• Robert Israel, Proof of comments by Hilliard (also conjectured by Detlefs) and Ibrishimova
• Index to sequences related to decomposition of primes in quadratic fields

Crossrefs

Cf. A001132 (complement from the odd primes), A007521 (subsequence), A038873, A226523.

Programs

Magma

[3] cat [p: p in PrimesUpTo (600) | p^2 mod 48 eq 25]; // Vincenzo Librandi, May 23 2016

Maple

for n from 2 to 563 do if(ithprime(n)^2 mod 48 = 25) then print(ithprime(n)) fi od. # Gary Detlefs, Dec 29 2011

Mathematica

Select[Prime @ Range[2, 105], JacobiSymbol[2, # ] == -1 &] (* Robert G. Wilson v, Dec 15 2005 *)
Select[Union[8Range[100] - 5, 8Range[100] - 3], PrimeQ[#] &] (* Alonso del Arte, May 22 2016 *)
Select[Prime[Range[150]],MemberQ[{3,5},Mod[#,8]]&] (* Harvey P. Dale, Mar 02 2022 *)

PARI

is(n)=isprime(n) && (n%8==3 || n%8==5) \\ Charles R Greathouse IV, Mar 21 2016