A003631 Primes congruent to 2 or 3 modulo 5.

2, 3, 7, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 97, 103, 107, 113, 127, 137, 157, 163, 167, 173, 193, 197, 223, 227, 233, 257, 263, 277, 283, 293, 307, 313, 317, 337, 347, 353, 367, 373, 383, 397, 433, 443, 457, 463, 467, 487, 503, 523, 547, 557, 563, 577

Offset: 1

Author

N. J. A. Sloane, Mira Bernstein

Keywords

• nonn
• easy
• nice

Comments

For n>1, sequence gives primes ending in 3 or 7. - Lekraj Beedassy, Oct 27 2003

Inert rational primes in Q(sqrt 5), or, p is not a square mod 5. [See e.g., Hasse, Legendre symbol (5|p) = -1, Hardy and Wright, Theorem 257 (2), p. 222, and Dodd Appendix B, pp. 128 - 150, primes p < 32771 with (p,0). - Wolfdieter Lang, Jun 16 2021]

Primes for which the period of the Fibonacci sequence mod p divides 2p+2.

Let F(n) be the n-th Fibonacci number for n=1,2,3,... (A000045). F(n) mod p (a prime) generates a periodic sequence. This sequence may be generated as follows: F(p-1)* F(p) mod p = p-1. E.g., p=7: F(6) * F(7) mod 7 = 8 * 13 mod 7 = 6 = p-1. - Louis Mello (Mellols(AT)aol.com), Feb 09 2001

These are also the primes p that divide Fibonacci(p+1). - Jud McCranie

Also primes p such that p divides F(2p+1)-1; such that p divides F(2p+3)-1; such that p divides F(3p+1)-1. - Benoit Cloitre, Sep 05 2003

Primes p such that the polynomial x^2-x-1 mod p has no zeros; i.e., x^2-x-1 is irreducible over the integers mod p. - T. D. Noe, May 02 2005

Primes p such that (1-x^5)/(1-x) is irreducible over GF(p). - Joerg Arndt, Aug 10 2011

Primes p such that p does not divide Sum_{i=1..p-1} Fibonacci(i)^2 = A001654(p-1). - Arkadiusz Wesolowski, Jul 23 2012

The prime 2 and primes p such that p^2 mod 10 = 9. - Richard R. Forberg, Aug 28 2013

Primes p such that 5 divides sigma(p^3), cf. A274397. - M. F. Hasler, Jul 10 2016

References

• F. W. Dodd, Number Theory in the Quadratic Field with Golden Section Unit, Polygon Publishing House, Passaic, NJ 07055, 1983, Appendix B, pp. 128 - 150.
• G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Chap. X, p. 150, Chap. XV, Theorem 257 (2), p. 222, Oxford University Press, Fifth edition.
• H. Hasse, Number Theory, Springer-Verlag, NY, 1980, p. 498.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• N. N. Vorob'ev, Fibonacci Numbers, Pergamon Press, 1961.

Links

• T. D. Noe, Table of n, a(n) for n = 1..1000
• Henri Darmon, Andrew Wiles's Marvelous Proof, Notices of the AMS (2017), Volume 64, Number 3 pp. 209-216. See p. 211.
• Index to sequences related to decomposition of primes in quadratic fields

Crossrefs

Primes in A047221.

Cf. A000040.

Cf. A000045, A001654.

Cf. A274397.

Programs

Haskell

a003631 n = a003631_list !! (n-1)
a003631_list = filter ((== 1) . a010051') a047221_list
-- Reinhard Zumkeller, Nov 27 2012, Jul 19 2011

Magma

[ p: p in PrimesUpTo(1000) | p mod 5 in {2, 3} ]; // Vincenzo Librandi, Aug 07 2012

Mathematica

Select[ Prime[Range[106]], MemberQ[{2, 3}, Mod[#, 5]] &] (* Robert G. Wilson v, Sep 12 2011 *)
a[ n_] := If[ n < 1, 0, Module[{c = 0, m = 0}, While[ c < n, If[ PrimeQ[++m] && KroneckerSymbol[5, m] == -1, c++]]; m]]; (* Michael Somos, Nov 24 2018 *)

PARI

list(lim)=select(n->n%5==2||n%5==3,primes(primepi(lim))) \\ Charles R Greathouse IV, Jul 25 2011

PARI

{a(n) = if( n < 1, 0, my(c ,m); while( c < n, if( isprime(m++) && kronecker(5, m) == -1, c++)); m)}; /* Michael Somos, Aug 14 2012 */

Formula

a(n) ~ 2n log n. - Charles R Greathouse IV, Jun 19 2017