TY - JOUR

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

AU - Luca, Florian

AU - Shparlinski, Igor E.

PY - 2006/12/18

Y1 - 2006/12/18

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=34948839513&partnerID=8YFLogxK

U2 - 10.1016/S0019-3577(06)81037-2

DO - 10.1016/S0019-3577(06)81037-2

M3 - Article

VL - 17

SP - 611

EP - 625

JO - Indagationes Mathematicae

JF - Indagationes Mathematicae

SN - 0019-3577

IS - 4

ER -