Pseudoprime values of the Fibonacci sequence, polynomials and the Euler function

Florian Luca*, Igor E. Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


We show that if α > 1 is any fixed integer, then for a sufficiently large x > 1, the nth Fibonacci number Fn is a base α pseudopfime only for at most (4 + o(1))π(x) of posifive integers n ≤ x. The same result holds for Mersenne numbers 2n - 1 and for one more general class of Lucas sequences. A slight modification of our method also leads to similar results for polynomial sequences f(n), where f {small element of} ℤ[X]. Finally, we use a different technique to get a much sharper upper bound on the counting fimction of the positive integers n such that φ(n) is a base α pseudoprime, where φ is the Euler function.

Original languageEnglish
Pages (from-to)611-625
Number of pages15
JournalIndagationes Mathematicae
Issue number4
Publication statusPublished - 18 Dec 2006


Dive into the research topics of 'Pseudoprime values of the Fibonacci sequence, polynomials and the Euler function'. Together they form a unique fingerprint.

Cite this