3
$\begingroup$

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?

$\endgroup$
5
  • $\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$ May 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$ May 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$ May 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$ May 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$ May 3, 2022 at 17:47

2 Answers 2

7
$\begingroup$

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

$\endgroup$
2
  • $\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
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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