For a given $a\in \mathbb{Z}$, define $P(a)$ to be the set of all prime numbers dividing $a$. Also define $\mathcal{P}$ to be the set of all prime numbers. Let $a,b,c\in \mathbb{Z}\setminus \{0\}$ be such that neither $\frac{b}{c}$ nor $\frac{c}{b}$ is a power of $a$. Then is it true that $$\mathcal{P}\setminus\cup_{n\in \mathbb{N}}P(ca^n-b)$$ is an infinite set?
-
$\begingroup$ Simple heuristic: for an arbitrary prime $p$ coprime to $abc$, the probability that $p \in \cup P(ca^n - b)$ is $\frac{\operatorname{ord}_p(a)}{p} \le \frac{\varphi(p-1)}{p}$. $\endgroup$– Peter TaylorMay 3, 2022 at 8:25
-
$\begingroup$ @PeterTaylor I am not sure how your statement answers the question above. Would it be possible for you to elaborate? $\endgroup$– ShyamalSayakMay 3, 2022 at 15:18
-
$\begingroup$ Heuristically, at least half of all primes will survive the filter. The tricky part is turning that into an unconditional proof that there are no $a,b,c$ which are somehow exceptional and only allow a finite number of primes through. $\endgroup$– Peter TaylorMay 3, 2022 at 15:31
-
$\begingroup$ @PeterTaylor I don't really need to allow finitely many primes through. All I need is the complement to be infinite. $\endgroup$– ShyamalSayakMay 3, 2022 at 16:10
-
$\begingroup$ I think we're speaking at cross purposes. What you call "the complement" is what I call "the primes which survive the filter" or "the primes which are allowed through". $\endgroup$– Peter TaylorMay 3, 2022 at 17:47
2 Answers
Yes. This follows from a result of Corrales-Rodrigáñez and Schoof (see the paper here) solving the support problem of Erdős.
In particular, suppose that there are only finitely many primes $p$ that do not divide $ca^{n} - b$ for any $n$. Let $x = a$ and $y = b/c$. If $q$ is a prime that divides $ca^{n} - b$ for some $n$ and does not divide $c$ then we have $a^{n} \equiv \frac{b}{c} \pmod{q}$. Then if $k$ is an integer, $x^{k} = a^{k} \equiv 1 \pmod{q}$ implies $y^{k} \equiv (b/c)^{k} \equiv (a^{n})^{k} \equiv 1 \pmod{q}$. In particular, $x^{k} \equiv 1 \pmod{q}$ implies that $y^{k} \equiv 1 \pmod{q}$.
Theorem 1 of the paper cited above shows that if $F$ is a number field, $x, y \in F^{\times}$ have the property that for all integers $n$ and almost all prime ideals $p$ of the ring of integers of $F$, one has $y^{n} \equiv 1 \pmod{p}$ whenever $x^{n} \equiv 1 \pmod{p}$, then $y$ is a power of $x$.
This implies that $b/c$ is a (positive or negative) power of $a$.
-
$\begingroup$ If you are fixing an $n$ then $ca^n-b$ is already a fixed integer and so can only have finitely many prime factors. So your sentence "In particular, suppose that $\ldots$" is unclear to me. $\endgroup$ May 4, 2022 at 18:08
-
$\begingroup$ I don't mean to be fixing $n$. I've changed the first sentence of the second paragraph to hopefully be more clear. $\endgroup$ May 5, 2022 at 1:11
This was answered by Schinzel (essentially), and in the concrete form asked here by Jaeschke and Trost, references below.
Schinzel, A. On the congruence a^x≡b (mod p).
Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 8 (1960), 307–309.
https://mathscinet.ams.org/mathscinet-getitem?mr=125070
The more general case answering the question is here, the proof is elementary. (Note that the letters $a,b,c$ are in a different order).
Jaeschke, G.; Trost, E. Über die Nichtprimteiler von $ab^x+c$. (German) Elem. Math. 21 (1966), 30–32. https://www.e-periodica.ch/digbib/view?pid=edm-001%3A1966%3A21%3A%3A7#37
Mathscinet writes (https://mathscinet.ams.org/mathscinet-getitem?mr=190064): The following theorem is proved: If $a,b,c$ are integers, $(ac,b)=1, b≥2$ and either $|ac|≠a^2$ or $b≠b_1^2$, then there exist infinitely many primes p≡1 mod4 and q≡−1 mod4 not dividing $ab^x+c$ and $ab^{2x+1}+c$, respectively, for any integer $x$. {Reviewer's remark: The case $a=1, b≥1, c$ arbitrary was treated by the reviewer [Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 8 (1960), 307–309; MR0125070], who proved that the necessary and sufficient condition for the existence of infinitely many primes not dividing $b^x+c$ is that $c≠−b^k$. A slight modification of that proof gives as the necessary and sufficient condition in the present general case $c≠−ab^k$.}
Other comments (written earlier), with further references:
The values $U_n=c a^n-b$ can be expressed by a linear recurrence. $U_{n+1}=a(U_n +b)-b$.
Some cases, related to the order of an element mod $p$, were studied by Hasse:
H. Hasse, Über die Dichte der Primzahlen p, für die eine vorgegebene ganzrationale Zahl a≠0 von gerader bzw. ungerader Ordnung mod p ist', Math. Ann. 166 (1966), 19-23. MR0205975 https://eudml.org/doc/161442
Example: If $p|a^n+1$, then $a^n=-1 \bmod p$, and the order of $a$ is even. Hasse proved for example, that the natural density of the primes dividing some number of the form $2^n+1$ is $17/24$. (With an explicit density $<1$ it is clear that the complement of the other other primes is infinite.)
Odoni and others generalized this: Odoni, R. W. K. A conjecture of Krishnamurthy on decimal periods and some allied problems. J. Number Theory 13 (1981), no. 3, 303-319. https://mathscinet.ams.org/mathscinet-getitem?mr=634201
Wiertelak, K. On the density of some sets of primes. IV. Acta Arith. 43 (1984), no. 2, 177-190. https://mathscinet.ams.org/mathscinet-getitem?mr=736730
A much more general treatment is: Ballot, Christian Density of prime divisors of linear recurrences. (English summary) Mem. Amer. Math. Soc. 115 (1995), no. 551, viii+102 pp. https://mathscinet.ams.org/mathscinet-getitem?mr=1257079
There is a lot of literature on prime divisors dividing the value of a recurrence of order 2, e.g. by M. Ward, J. Lagarias https://mathscinet.ams.org/mathscinet-getitem?mr=789184 , P.Moree)
Related is: Shparlinski, Igor E. Prime divisors of sparse integers. Period. Math. Hungar. 46 (2003), no. 2, 215--222.
The book below, sections 6.2 and 6.3, contains relevant information.
Everest, Graham; van der Poorten, Alf; Shparlinski, Igor; Ward, Thomas Recurrence sequences. Mathematical Surveys and Monographs, 104. American Mathematical Society, Providence, RI, 2003. xiv+318 pp.