Fix a positive integer $a>1$ and let $f\in\mathbb{Z}[x]$ be a polynomial with positive leading coefficient. We define a set $S$ of positive integers, $$ S=\{n\in\mathbb{Z}^+:n\mid a^{f(n)}1\}. $$ Question is, can we compute the density of $S$, that is, $$ \lim_{n\to\infty}\frac{S\cap \{1,2,\dots,n\}}{n}? $$ I believe that the answer should be $0$, yet I don't have a proof.

$\begingroup$ Possible strategy: (1) for a typical prime $p$, most arithmetic progressions modulo $p$ contain only integers $n$ for which $p\nmid f(n)$; (2) most integers in any such arithmetic progression have the property that $p$ divides the order of $a$ modulo $n$. Then an adhoc density bound, or indeed the large sieve, should give a nontrivial upper bound on the density of $S$. There should be some examples in the literature about integers $n$ for which $n \mid (a^n1)$. $\endgroup$– Greg MartinFeb 22, 2019 at 19:18
1 Answer
Fix $\varepsilon>0$ and choose large prime $q>5\varepsilon^{1} \cdot \deg(f)$ such that $f$ is nontrivial modulo $q$ (then $f$ has at most $\deg(f)$ roots modulo $q$) and additionally such that $a$ is not a $q$th perfect power. Say that a prime $p>q$ is $q$appropriate if $a$ is not $q$th power modulo $p$. By Chebotarev density theorem the $q$appropriate primes have positive density. Thus we may choose $q$appropriate primes $p_1,\dots,p_m$ such that $\prod_{i=1}^m (11/p_i)<\varepsilon/5$. Note that if $n$ divides $a^{f(n)}1$, then either $q$ divides $f(n)$ (density of such $n$ does not exceed $\deg(f)/q<\varepsilon/5$), or neither $p_i$ divides $n$. [Indeed, if $p_ina^{f(n)}1$, but $q$ does not divide $f(n)$, we may find $s$ such that $sf(n)+1$ is divisible by $q$, that yields $a\equiv a^{1+sf(n)} \pmod {p_i}$, so $a$ is a $q$th power modulo $p_i$, a contradiction.] The density of such $n$'s is exactly $\prod_{i=1}^m (11/p_i)<\varepsilon/5$. So $S$ is covered by finitely many arithmetic progressions with sum of densities less than $\varepsilon$.