# Divisors of shifted geometric progressions

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.

• 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 Commented May 1, 2020 at 0:07
• @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). Commented May 1, 2020 at 10:43

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).

• 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. Commented May 1, 2020 at 10:45