A003147 Primes p with a Fibonacci primitive root g, i.e., such that g^2 = g + 1 (mod p).

5, 11, 19, 31, 41, 59, 61, 71, 79, 109, 131, 149, 179, 191, 239, 241, 251, 269, 271, 311, 359, 379, 389, 409, 419, 431, 439, 449, 479, 491, 499, 569, 571, 599, 601, 631, 641, 659, 701, 719, 739, 751, 821, 839, 929, 971, 1019, 1039, 1051, 1091, 1129, 1171, 1181, 1201, 1259, 1301

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

Primes p with a primitive root g such that g^2 = g + 1 (mod p).

Not the same as primes with a Fibonacci number as primitive root; cf. A083701. - Jonathan Sondow, Feb 17 2013

For all except the initial term 5, these are numbers such that the Pisano period equals 1 less than the Pisano number, i.e., where A001175(n) = n-1. - Matthew Goers, Sep 20 2013

As shown in the paper by Brison, these are also the primes p such that there is a Fibonacci-type sequence (mod p) that begins with (1,b) and encounters all numbers less than p in the first p-1 iterations (for some b). - T. D. Noe, Feb 26 2014

Shanks (1972) conjectured that the relative asymptotic density of this sequence in the sequence of primes is 27*c/38 = 0.2657054465..., where c is Artin's constant (A005596). The conjecture was proved on the assumption of a generalized Riemann hypothesis by Lenstra (1977) and Sander (1990). - Amiram Eldar, Jan 22 2022

Examples

			3 is a primitive root mod 5, and 3^2 = 3 + 1 mod 5, so 5 is a member. - _Jonathan Sondow_, Feb 17 2013
		

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 1000 terms from Noe)
• Bob Bastasz, Lyndon words of a second-order recurrence, Fibonacci Quarterly, Vol. 58, No. 5 (2020), pp. 25-29.
• Owen J. Brison, Complete Fibonacci sequences in finite fields, Fibonacci Quarterly, Vol. 30, No. 4 (1992), pp. 295-304.
• Alexandru Gica, Quadratic Residues in Fibonacci Sequences, Fibonacci Quart., Vol. 46/47, No. 1 (2008/2009), pp. 68-72. See Theorem 5.1.
• Liang-Chung Hsia, Hua-Chieh Li, and Wei-Liang Sun, Certain Diagonal Equations and Conflict-Avoiding Codes of Prime Lengths, arXiv:2302.00920 [math.NT], 2023.
• H. W. Lenstra, Jr., On Artin's conjecture and Euclid's algorithm in global fields, Invent. Math., Vol. 42 (1977), pp. 202-224; alternative link.
• J. W. Sander, On Fibonacci primitive roots, Fibonacci Quarterly, Vol. 28, No. 1 (1990), pp. 79-80.
• Daniel Shanks, Fibonacci primitive roots, end of article, Fibonacci Quarterly, Vol. 10, No. 2 (1972), pp. 163-168, 181.
• Daniel Shanks and Larry Taylor, An Observation of Fibonacci Primitive Roots, Fibonacci Quarterly, Vol. 11, No. 2 (1973), pp. 159-160.
• Index entries for primes by primitive root.

Crossrefs

Subsequence of A038872.

Cf. A001175, A005596, A083701.

See also A106535.

Programs

Maple

filter:=proc(n) local g,r;
if not isprime(n) then return false fi;
r:= [msolve(g^2 -g - 1, n)][1];
numtheory:-order(rhs(op(r)),n) = n-1
end proc:
select(filter, [5,seq(seq(10*i+j,j=[1,9]),i=1..1000)]); # Robert Israel, May 22 2015

Mathematica

okQ[p_] := AnyTrue[PrimitiveRootList[p], Mod[#^2, p] == Mod[#+1, p]&]; Select[Prime[Range[300]], okQ] (* Jean-François Alcover, Jan 04 2016 *)

PARI

is(n)=if(kronecker(5,n)<1||!isprime(n), return(n==5)); my(s=sqrt(Mod(5,n))); znorder((1+s)/2)==n-1 || znorder((1-s)/2)==n-1 \\ Charles R Greathouse IV, May 22 2015

Extensions

More terms from David W. Wilson

Cross-reference from Charles R Greathouse IV, Nov 05 2009

Definition clarified by M. F. Hasler, Jun 05 2018