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

%I #78 Jan 29 2024 11:01:18

%S 2,7,17,23,31,41,47,71,73,79,89,97,103,113,127,137,151,167,191,193,

%T 199,223,233,239,241,257,263,271,281,311,313,337,353,359,367,383,401,

%U 409,431,433,439,449,457,463,479,487,503,521,569,577,593,599,601,607,617

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

%C Same as A001132 except for initial term.

%C Primes p such that x^2 = 2 has a solution mod p.

%C 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

%C 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

%C After a(1) = 2, these are the primes p such that p^4 == 1 (mod 96). - _Gary Detlefs_, Jan 22 2014

%C Also primes of the form 2v^2 - u^2. For example, 23 = 2*4^2 - 3^2. - _Jerzy R Borysowicz_, Oct 27 2015

%C Prime factors of A008865 and A028884. - _Klaus Purath_, Dec 07 2020

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

%H Nathaniel Johnston, <a href="/A038873/b038873.txt">Table of n, a(n) for n = 1..10000</a>

%H K. S. Brown, <a href="http://www.mathpages.com/home/kmath358.htm">Pythagorean graphs</a>.

%H 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 <a href="/index/Pri#smp">Index entries for related sequences</a>

%F a(n) ~ 2n log n. - _Charles R Greathouse IV_, Nov 29 2016

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

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

%o (Magma) [ p: p in PrimesUpTo(617) | IsSquare(R!2) where R:=ResidueClassRing(p) ]; // _Klaus Brockhaus_, Dec 02 2008

%o (PARI) is(n)=isprime(n) && issquare(Mod(2,n)) \\ _Charles R Greathouse IV_, Apr 23 2015

%o (PARI) is(n)=abs(centerlift(Mod(n,8)))<3 && isprime(n) \\ _Charles R Greathouse IV_, Nov 14 2017

%Y Cf. A057126, A087780, A226523, A003629 (complement).

%Y Primes in A035251.

%Y 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, ...

%K nonn,easy

%O 1,1

%A _N. J. A. Sloane_