MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In Theorem 2 of their paper, "Pseudoprime values of the Fibonacci sequence, polynomials and the Euler function", Indagationes Mathematicae, Volume 17, Issue 4, pp. 611--625, Luca and Shparlinski show that for a fixed polynomial $f(x)\in \mathbb{Z}[x]$ and fixed base $a>1$, the number of $1\leq n \leq x$ for which $f(n)$ is pseudoprime to the base $a$ is

$$ \ll x\frac{\log \log x}{\log x}. $$

Is there a lower bound that would allow one to tell whether, for any $f$, any $a>1$ is a base to which infinitely many $f(n)$ are pseudoprime? (If $f(n)=n$ there is a lower bound due to Pomerance.) In the absence of such a lower bound, is there any guide as to how small one may take $a$ relative to $n$, and hence $f(n)$, for general $f$?

If $f$ is a cyclotomic polynomial $\Phi_r(n)$, $r$ an odd prime, and the base $a$ is allowed to vary, i.e., take $a=n$ for $n$ in some congruence class, then a result of Cipolla, mentioned here, gives that

$$ n^{\Phi_r(n)-1} \equiv 1 \bmod \Phi_r(n) $$

provided $n$ is in the right congruence classes. Assuming Bateman-Horn, one then has examples of $a$ of size $n$ to which $f(n)=\Phi_r(n)$ are pseudoprime. Are there any explicit constructions that can give $a=o(n)$ for an arbitrary $f$?

Thank you!

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.