Pseudoprime values of the Fibonacci sequence, polynomials and the Euler function (Q2385794): Difference between revisions

A base \(a\) pseudoprime (\(a\in\mathbb{N}\), \(>1\)) is a composite integer \(n\) such that \(n\mid a^n- a\). The authors prove, that the \(n\)th Fibonacci number \(F_n\) is a base \(a\) pseudoprime only for at most \((4+ o(1))\pi(x)\) positive integers \(n\leq x\) (\(x\) sufficiently large). The same result holds for one general class of Lucas sequences such as the Mersenne numbers \(2^n- 1\), and polynomial sequences \(f(n)\), where \(f\in\mathbb{Z}[X]\). By a different method they get a sharper upper bound of the counting function on positive integers \(n\), such that \(\varphi(n)\) is a base \(a\) pseudoprime (\(\varphi\) is the Euler function).