

A002313


Primes congruent to 1 or 2 modulo 4; or, primes of form x^2 + y^2; or, 1 is a square mod p.
(Formerly M1430 N0564)


127



2, 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, 101, 109, 113, 137, 149, 157, 173, 181, 193, 197, 229, 233, 241, 257, 269, 277, 281, 293, 313, 317, 337, 349, 353, 373, 389, 397, 401, 409, 421, 433, 449, 457, 461, 509, 521, 541, 557, 569, 577, 593, 601, 613, 617
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Or, primes p such that x^2  p*y^2 represents 1.
Primes which are not Gaussian primes (meaning not congruent to 3 mod 4).
Every Fibonacci prime (with the exception of F(4) = 3) is in the sequence. If p = 2n+1 is the prime index of the Fibonacci prime, then F(2n+1) = F(n)^2 + F(n+1)^2 is the unique representation of the prime as sum of two squares.  Sven Simon, Nov 30 2003
Except for 2, primes of the form x^2 + 4y^2. See A140633.  T. D. Noe, May 19 2008
Primes p such that for all p > 2, p XOR 2 = p + 2.  Brad Clardy, Oct 25 2011
Greatest prime divisor of r^2 + 1 for some r.  Michel Lagneau, Sep 30 2012
Empirical result: a(n), as a set, compose the prime factors of the family of sequences produced by A005408(j)^2 + A005408(j+k)^2 = (2j+1)^2 + (2j+2k+1)^2, for j >= 0, and a given k >= 1 for each sequence, with the addition of the prime factors of k if not already in a(n).  Richard R. Forberg, Feb 09 2015
Primes such that when r is a primitive root then pr is also a primitive root.  Emmanuel Vantieghem, Aug 13 2015
Primes of the form (x^2 + y^2)/2. Note that (x^2 + y^2)/2 = ((x+y)/2)^2 + ((xy)/2)^2 = a^2 + b^2 with x = a + b and y = a  b. More generally, primes of the form (x^2 + y^2) / A001481(n) for every fixed n > 1.  Thomas Ordowski, Jul 03 2016
Numbers n such that ((n2)!!)^2 == 1 (mod n).  Thomas Ordowski, Jul 25 2016
Primes p such that (p1)!! == (p2)!! (mod p).  Thomas Ordowski, Jul 28 2016
The product of 2 different terms (x^2 + y^2)(z^2 + v^2) = (xz + yv)^2 + (xv  yz)^2 is sum of 2 squares (A000404) because (xv  yz)^2 > 0. If x were equal to yz/v then (x^2 + y^2)/(z^2 + v^2) would be equal to ((yz/v)^2 + y^2)/(z^2 + v^2) = y^2/v^2 which is not possible because (x^2 + y^2) and (z^2 + v^2) are prime numbers. For example, (2^2 + 5^2)(4^2 + 9^2) = (2*4 + 5*9)^2 + (2*9  5*4)^2.  Jerzy R Borysowicz, Mar 21 2017


REFERENCES

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 872.
David A. Cox, "Primes of the Form x^2 + n y^2", Wiley, 1989.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, p. 219, th. 251, 252.
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).


LINKS



FORMULA



EXAMPLE

13 is in the sequence since it is prime and 13 = 4*3 + 1. Also 13 = 2^2 + 3^2. And 1 is a square (mod 13): 1 + 2*13 = 25 = 5^2. Of course, only the first term is congruent to 2 (mod 4).  Michael B. Porter, Jul 04 2016


MAPLE

with(numtheory): for n from 1 to 300 do if ithprime(n) mod 4 = 1 or ithprime(n) mod 4 = 2 then printf(`%d, `, ithprime(n)) fi; od:
# alternative
option remember ;
local a;
if n = 1 then
2;
elif n = 2 then
5;
else
for a from procname(n1)+4 by 4 do
if isprime(a) then
return a ;
end if;
end do:
end if;
end proc:


MATHEMATICA

fQ[n_] := Solve[x^2 + 1 == n*y^2, {x, y}, Integers] == {}; Select[ Prime@ Range@ 115, fQ] (* Robert G. Wilson v, Dec 19 2013 *)


PROG

(Haskell)
a002313 n = a002313_list !! (n1)
a002313_list = filter ((`elem` [1, 2]) . (`mod` 4)) a000040_list
(Magma) [p: p in PrimesUpTo(700)  p mod 4 in {1, 2}]; // Vincenzo Librandi, Feb 18 2015


CROSSREFS



KEYWORD

nonn,easy,nice


AUTHOR



EXTENSIONS



STATUS

approved



