For integers $a,b,k$ with $a \geq 1$ and $k\geq 2$, consider the shifted geometric progression $n_i = ak^i + b$. I would like to understand the set of integers (prime or otherwise) that divide at least one of the $n_i$'s. More precisely, let $$ D = D_{a,b,k} = \{ d \in \mathbb{N} \ : \ \text{there exists } i \geq 1 \text{ with } d \mid n_i \}, $$ $$ P = P_{a,b,k} = \{ p \ : \ p \text{ is prime and there exists } i \geq 1 \text{ with } p \mid n_i \}. $$ Questions:

  1. Is it known the set $P$ has positive relative density inside the primes?

  2. Barring a positive answer to 1., what can be said about the sizes of $D$ and $P$?

(It is certainly possible that $D$ has asymptotic density $0$, e.g. by letting $a,b$ and $k$ be squares. If the answer to the first question is positive then $\# D \cap [1,x] \geq \# P \cap [1,x] \gg x/\log x$. In the second question I'm hoping that perhaps a weaker asymptotic is true, such as $\# D \cap [1,x] \gg x^{1-\varepsilon}$.)

Context: It would follow from Artin's conjecture on primitive roots that $k$ is a primitive root for a positive proportion of the primes, and for each such prime $p$ there exists $i$ with $k^i \equiv -b/a$, whence $p \mid n_i$ (at least, as long as $p$ does not divide $ab$). Hence, if we believe Artin's conjecture then $P$ has positive density inside the primes.

One can also show by purely elementary methods that for each $C$ there exists $i$ such that $n_i$ has $>C$ prime divisors. Hence, $P$ is infinite. Here is a sketch: Assume, as we may do without loss of generality, that $b$ is coprime to $k$ (else, replace $a$ with $ak^{i_0}/d$, $b$ with $b/d$, and $i$ with $i-i_0$ where $d = \gcd(k^{i_0},b)$ for some large integer $i_0$). This assumption ensures that $n_i$ ($i \geq 1$) are coprime to $k$. Construct a sequence $i_j$ where $i_1$ is arbitrary, and $i_{j+1} = i_j + \varphi(n_{i_j}^2)$, so that $n_{i_{j+1}} \equiv n_{i_j} \bmod n_{i_j}^2$. This is set up so that $n_{i_{j+1}}/n_{i_j}$ is an integer coprime to $n_{i_j}$, and consequently $n_{i_j}$ has at least $j$ distinct prime factors.

  • 1
    $\begingroup$ You seem to be asking about the "two-variable Artin conjecture". Unfortunately the known (unconditional) results seem much weaker than what you are hoping for; I think the state of the art is arxiv.org/abs/1711.06410 $\endgroup$ May 1, 2020 at 0:07
  • $\begingroup$ @so-calledfriendDon: Thank you! Yes, it seems like what I'm asking is very closely related: If I understand correctly, the case of my question where $b/a \in \mathbb{Z}$ and we only care about prime divisors is corresponds precisely to Theorem 1.1 in the preprint you attached, while Theorem 2.1 is more general than my question (since $ak^i + b$ satisfies a binary recurrence). $\endgroup$ May 1, 2020 at 10:43

1 Answer 1


This does not fully answer the question, but gives several links to some related literature. Most papers below study if the order of an element mod $p$ is odd or even, (or more general). Therefore the links below study the cases $a=1, b=1$ or $b=-1$ in your notation. Shparlinski's paper is more general, but primarily studies related sequences with more than 2 summands.

a) The following two papers by Hasse give at least some special cases such as prime divisors of the sequence $k^n+1$, ($k$ is fixed, $n \in \mathbf{N}$). In particular Hasse proved that the Dirichlet density of primes dividing an integer of the type $2^n+1$ is $17/24$. Note: if $p|(2^n+1)$, then $2^n\equiv -1 \bmod p$, and the order of $2$ modulo $p$ is even.

H. HASSE, Über die Dichte der Primzahlen p, für die eine vorgegebene ganzrationale Zahl $a\neq 0$ von gerader bzw. ungerader Ordnung mod p ist. Math. Ann. 166 (1966), 19-23. http://www.digizeitschriften.de/dms/img/?PID=GDZPPN002296616

H. HASSE, Über die Dichte der Primzahlen p, für die eine vorgegebene rationale Zahl $a\neq 0$ von durch eine vorgegebene Primzahl $l \neq 2$ teilbarer bzw. unteilbarer Ordnung mod $p$ ist. Math. Ann. 162 (1965), 74-76 http://www.digizeitschriften.de/dms/img/?PID=GDZPPN002295253

b) Odoni proved corresponding results for natural density. Journal of Number Theory Volume 13, Issue 3, August 1981, Pages 303-319 A conjecture of Krishnamurthy on decimal periods and some allied problems, https://www.sciencedirect.com/science/article/pii/0022314X81900160

In some cases he got positive relative prime density, in other cases 0-density.

c) On RH (related to Artin's conjecture Stephens, P. J. Prime divisors of second-order linear recurrences. I. J. Number Theory 8 (1976), no. 3, 313–332.

d) Shparlinski, Igor E. Prime divisors of sparse integers. Period. Math. Hungar. 46 (2003), no. 2, 215–222. https://link.springer.com/article/10.1023%2FA%3A1025996312037

e) Hooley's book "Application of sieve methods to the theory of numbers" has some information on prime factors of $2^n+b$.

f) Prime divisors of certain recurrent sequences have been studied e.g. by Ballot, and Moree.

Finally, I believe that the case $|b| \neq 1$ is more difficult, as there is less algebraic structure (such as order of an element).

  • $\begingroup$ Thank you! That's very relevant - and the problem at the level of generality I was hoping for appears to be much harder than I anticipated. $\endgroup$ May 1, 2020 at 10:45

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.