A set with zero density

Question

Let $a>1$ be a positive integer and $f\in \mathbb{Z}[x]$ with positive leading coefficient. Let $S$ be the set of integers $n$ such that $$n \mid a^{f(n)}-1.$$ Prove that $S$ has density $0$; that is, prove that $\displaystyle\lim_{n\rightarrow \infty} \frac{|S\cap \{1,...,n\}|}{n}=0$.

I have not made any improvement on this one. Help!! Thanks. Sorry if this is too easy for this site but I haven't got any answer to this so tried posting this here. Thanks again.

Answer 1

Given that this is a contest problem, presumably there's an "elementary" solution. For a connection with research, see (e.g.) this paper of Luca and Ballot: http://nyjm.albany.edu/j/2006/12-3.html. They show that if $f$ is irreducible of degree $\ge 2$, then the primes dividing $a^{f(n)}-1$ for some $n$ form a set of relative density zero.

For these $f$, their result (along with a sieve) shows the following stronger theorem: The set of $m$ that divide $a^{f(n)}-1$ for some $n$ has asymptotic density zero. (This is much stronger since we don't insist that $n=m$.)

Answer 2

Minor observation: If $n$ divides $a^{f(n)}-1$, then $a$ and $n$ have no common factors.

Perhaps multiple uses of Fermat's little theorem will help. Fix $a\geq 2$. Let's simplify and consider $f(n)$ of the form $f(n) = mn^b$ for positive integers $m, b$. Suppose $n=rp^z$ where $p$ is prime and $r,z$ are positive integers. We want to consider $n$ such that $a^{f(n)}-1$ is divisible by $n$, so $a^{f(n)}-1$ is divisible by $p$. So:

$0$
= $a^{f(n)} -1$ (mod p)
= $a^{mn^b}-1$ (mod p)
= $a^{mr^bp^{zb}} - 1$ (mod p)
= $a^{mr^b} -1$ (mod p) [Repeated applications of Fermat]
= $a^{f(r)}-1$ (mod p)

So we need $a^{f(r)}-1$ to be divisible by $p$. This should also hold when $f(n)$ has multiple terms.

Thus, given $r$, only primes $p$ in the finite set $\{2, ..., a^{f(r)}-1\}$ can work. Unfortunately, this does not solve the problem as I had hoped.

---

Another minor observation: Since $n$ and $a$ have no common factors, then $a$ and $p$ have no common factors and $a^{p-1}=1$ (mod $p$). So $a^{mod(f(r),p-1)}=1$ (mod $p$).