cp's OEIS Frontend

A002313 Primes congruent to 1 or 2 modulo 4; or, primes of form x^2 + y^2; or, -1 is a square mod p.

%I A002313 M1430 N0564 #147 Jul 02 2025 16:01:54
%S A002313 2,5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,
%T A002313 193,197,229,233,241,257,269,277,281,293,313,317,337,349,353,373,389,
%U A002313 397,401,409,421,433,449,457,461,509,521,541,557,569,577,593,601,613,617
%N A002313 Primes congruent to 1 or 2 modulo 4; or, primes of form x^2 + y^2; or, -1 is a square mod p.
%C A002313 Or, primes p such that x^2 - p*y^2 represents -1.
%C A002313 Primes which are not Gaussian primes (meaning not congruent to 3 mod 4).
%C A002313 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
%C A002313 Except for 2, primes of the form x^2 + 4y^2. See A140633. - _T. D. Noe_, May 19 2008
%C A002313 Primes p such that for all p > 2, p XOR 2 = p + 2. - _Brad Clardy_, Oct 25 2011
%C A002313 Greatest prime divisor of r^2 + 1 for some r. - _Michel Lagneau_, Sep 30 2012
%C A002313 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
%C A002313 Primes such that when r is a primitive root then p-r is also a primitive root. - _Emmanuel Vantieghem_, Aug 13 2015
%C A002313 Primes of the form (x^2 + y^2)/2. Note that (x^2 + y^2)/2 = ((x+y)/2)^2 + ((x-y)/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
%C A002313 Numbers n such that ((n-2)!!)^2 == -1 (mod n). - _Thomas Ordowski_, Jul 25 2016
%C A002313 Primes p such that (p-1)!! == (p-2)!! (mod p). - _Thomas Ordowski_, Jul 28 2016
%C A002313 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
%D A002313 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.
%D A002313 David A. Cox, "Primes of the Form x^2 + n y^2", Wiley, 1989.
%D A002313 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.
%D A002313 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002313 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002313 Zak Seidov, <a href="/A002313/b002313.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)
%H A002313 Dario Alpern, <a href="https://www.alpertron.com.ar/FSQUARES.HTM">Online program that calculates sum of squares representation</a>
%H A002313 N. J. A. Sloane et al., <a href="https://oeis.org/wiki/Binary_Quadratic_Forms_and_OEIS">Binary Quadratic Forms and OEIS</a> (Index to related sequences, programs, references)
%H A002313 J. Todd, <a href="https://www.jstor.org/stable/2305526">A problem on arc tangent relations</a>, Amer. Math. Monthly, 56 (1949), 517-528.
%H A002313 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Fermats4nPlus1Theorem.html">Fermat's 4n+1 Theorem</a>
%H A002313 G. Xiao, <a href="https://wims.univ-cotedazur.fr/~wims/en_tool~number~twosquares.en.html">Two squares</a>
%H A002313 <a href="/index/Ga#gaussians">Index entries for Gaussian integers and primes</a>
%F A002313 a(n) ~ 2n log n. - _Charles R Greathouse IV_, Jul 04 2016
%F A002313 a(n) = A002331(n)^2  + A002330(n)^2. See crossrefs. - _Wolfdieter Lang_, Dec 11 2016
%e A002313 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
%p A002313 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:
%p A002313 # alternative
%p A002313 A002313 := proc(n)
%p A002313     option remember ;
%p A002313     local a;
%p A002313     if n = 1 then
%p A002313         2;
%p A002313     elif n = 2 then
%p A002313         5;
%p A002313     else
%p A002313         for a from procname(n-1)+4 by 4 do
%p A002313             if isprime(a) then
%p A002313                 return a ;
%p A002313             end if;
%p A002313         end do:
%p A002313     end if;
%p A002313 end proc:
%p A002313 seq(A002313(n),n=1..100) ; # _R. J. Mathar_, Feb 01 2024
%t A002313 Select[ Prime@ Range@ 115, Mod[#, 4] != 3 &] (* _Robert G. Wilson v_ *)
%t A002313 fQ[n_] := Solve[x^2 + 1 == n*y^2, {x, y}, Integers] == {}; Select[ Prime@ Range@ 115, fQ] (* _Robert G. Wilson v_, Dec 19 2013 *)
%o A002313 (PARI) select(p->p%4!=3, primes(1000)) \\ _Charles R Greathouse IV_, Feb 11 2011
%o A002313 (Haskell)
%o A002313 a002313 n = a002313_list !! (n-1)
%o A002313 a002313_list = filter ((`elem` [1,2]) . (`mod` 4)) a000040_list
%o A002313 -- _Reinhard Zumkeller_, Feb 04 2014
%o A002313 (Magma) [p: p in PrimesUpTo(700) | p mod 4 in {1,2}]; // _Vincenzo Librandi_, Feb 18 2015
%Y A002313 Apart from initial term, same as A002144. For values of x and y see A002330 and A002331.
%Y A002313 Cf. A033203, A038873, A038874, A045331, A008784, A057129, A084163, A084165, A137351.
%K A002313 nonn,easy,nice
%O A002313 1,1
%A A002313 _N. J. A. Sloane_
%E A002313 More terms from _Henry Bottomley_, Aug 10 2000
%E A002313 More terms from _James Sellers_, Aug 22 2000