Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.