A081264 Odd Fibonacci pseudoprimes: odd composite numbers k such that either (1) k divides Fibonacci(k-1) if k == +-1 (mod 5) or (2) k divides Fibonacci(k+1) if k == +-2 (mod 5).

323, 377, 1891, 3827, 4181, 5777, 6601, 6721, 8149, 10877, 11663, 13201, 13981, 15251, 17119, 17711, 18407, 19043, 23407, 25877, 27323, 30889, 34561, 34943, 35207, 39203, 40501, 50183, 51841, 51983, 52701, 53663, 60377, 64079, 64681

Offset: 1

Author

T. D. Noe, Mar 15 2003, Jun 09 2008

Keywords

• nice
• nonn

Comments

Lehmer shows that there are an infinite number of Fibonacci pseudoprimes (FPPs). In particular, the number Fibonacci(2p) is an FPP for all primes p > 5. Anderson lists over 5000 FPPs, while Jacobsen lists over 170000. The sequences A069106 and A069107 give k such that k divides Fibonacci(k-1) and k divides Fibonacci(k+1), respectively. See A141137 for even FPPs.

References

• R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, 2002, p. 131.
• Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1995, p. 127.
• Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 104.
• A. Witno, Theory of Numbers, BookSurge, North Charleston, SC; see p. 83.

Links

• P. G. Anderson and Dana Jacobsen, Table of n, a(n) for n = 1..10000 (first 5861 terms from P. G. Anderson)
• P. G. Anderson, Fibonacci pseudoprimes under 2,217,967,487 and their factors
• Dorin Andrica and Ovidiu Bagdasar, Recurrent Sequences: Key Results, Applications, and Problems, Springer (2020), p. 88.
• Dorin Andrica and Ovidiu Bagdasar, On Generalized Lucas Pseudoprimality of Level k, Mathematics (2021) Vol. 9, 838.
• Dorin Andrica, Vlad Crişan, and Fawzi Al-Thukair, On Fibonacci and Lucas sequences modulo a prime and primality testing, Arab Journal of Mathematical Sciences, 2017.
• Dana Jacobsen, Pseudoprime Statistics, Tables, and Data (includes terms through 7e12)
• E. Lehmer, On the infinitude of Fibonacci pseudoprimes, Fibonacci Quarterly, 2, 1964, pp. 229-230.
• Andrzej Rotkiewicz, Arithmetic progressions formed by pseudoprimes, Acta Mathematica et Informatica Universitatis Ostraviensis, vol. 8 (2000), issue 1, pp. 61-74.
• Eric Weisstein's World of Mathematics, Fibonacci Pseudoprime
• Wikipedia, Fibonacci pseudoprime
• Index entries for sequences related to pseudoprimes

Crossrefs

Cf. A069106, A069107, A141137.

Programs

Maple

filter:= proc(n) local M,r;
   uses LinearAlgebra:-Modular;
   if isprime(n) then return false fi;
   M:= Mod(n, [[1,1],[1,0]],float[8]);
   if n^2 mod 5 = 1 then r:= n-1 else r:= n+1 fi;
   M:= MatrixPower(n,M,r);
   M[1,2] = 0
end proc:select(filter, [2*i+1 $ i=1..10^5]); # Robert Israel, Aug 05 2015

Mathematica

lst={}; f0=0; f1=1; Do[f2=f1+f0; If[n>1&&!PrimeQ[n], If[MemberQ[{1, 4}, Mod[n, 5]], If[Mod[f0, n]==0, AppendTo[lst, n]]]; If[MemberQ[{2, 3}, Mod[n, 5]], If[Mod[f2, n]==0, AppendTo[lst, n]]]]; f0=f1; f1=f2, {n, 100000}]; lst
ocnQ[n_]:=CompositeQ[n]&&Which[Mod[n,5]==1,Divisible[Fibonacci[ n-1], n],Mod[n,5] == 4,Divisible[ Fibonacci[n-1],n],Mod[n,5]==2,Divisible[ Fibonacci[n+1],n], Mod[n,5]==3,Divisible[Fibonacci[n+1],n],True,False]; Select[Range[1,65001,2],ocnQ] (* Harvey P. Dale, Aug 23 2017 *)

Perl

use ntheory ":all"; foroddcomposites { $e = (0,-1,1,1,-1)[$%5]; say unless $e==0 || (lucas_sequence($, 1, -1, $+$e))[0] } 1e10; # _Dana Jacobsen, Aug 05 2015