1
$\begingroup$

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.

$\endgroup$
1
  • $\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 ad-hoc 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^n-1)$. $\endgroup$ Feb 22, 2019 at 19:18

1 Answer 1

2
$\begingroup$

Fix $\varepsilon>0$ and choose large prime $q>5\varepsilon^{-1} \cdot \deg(f)$ such that $f$ is non-trivial 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 (1-1/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_i|n|a^{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 (1-1/p_i)<\varepsilon/5$. So $S$ is covered by finitely many arithmetic progressions with sum of densities less than $\varepsilon$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.