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$.
The given hint is: first consider the set $S_p=S \cap {\{p,2p,...}\}$, where $p$ is a prime, and show $S_p$ has density $0$.The hint says this can be done by induction on $deg f$. But I am curious how to apply induction here, as the set $S$ differs greatly when $f$ changes.
After this key step, I know how to solve the remaining part, just deal with small primes and large primes independently.