Arbitrarily long arithmetic progressions

Question

Are there arbitrarily long arithmetic progressions in which all the prime factors of all the terms are at most $N$, for some $N$? Assume all the terms are positive and the sequence of terms is increasing.

I have proved that no such infinite sequence exists. Note the $N$ may vary from AP to AP. For infinite sequences let $\{a+nd\}_{n\ge 0}$ be the AP. $\text{gcd}(a,d)=s$ then $a+nd=s(x+ny)$ for some $x,y$ with $\text{gcd}(x,y)=1$ then by Dirichlet's theorem $\{x+ny\}_{n\ge 0}$ has infinitely many primes. Thus we have the prime factors of the sequence is unbounded and hence done. But I was thinking about this claim but nothing came in mind. Could someone help? Thanks a lot.

Answer 1

A simple proof is available as well. Pick p coprime to d and let t be such that td=1 mod p. Then, mod p, t times the arithmetic progression looks like a sequence of consecutive integers. Thus its length has to be less than p to avoid one of the terms being a multiple of p, which means the original progression also has to have fewer than p terms. So the collection of primes dividing a set of arbitrarily long arithmetic progressions must be infinite.

It has been noted by GH from MO that the above overlooks some subtleties; the following is more inspired by Euclid, and should leave no doubt remaining.

Let A be a set of arbitrarily long nonconstant arithmetic progressions. Thus for any integer m, we can find a member of A and extract from that (wlog) a positive increasing arithmetic progression of the form a +kd where a and d are coprime and k goes from 0 to m. Pick a finite set of primes M, set m equal to a large multiple of their product (so at least twice the product of primes of M) and then choose from A a progression and derive the progression a +kd with the properties above. I will show the existence of a prime divisor which is not in M and divides a member of the progression.

Now d may share some factors with the product of M, but as (a,d)=1, none of the factors of d will divide any of a +kd. To be safe, let us call M' that set of numbers in M which are coprime to d, and set their product to m'. So (m',d)=1, d is a unit mod m', and we can look at ta +tkd as k runs from 1 to m which is bigger than m'. As above, td=1 mod m'.

Modulo m', ta+tkd is ta+k, so ta+k is divisible by a factor of m' precisely when a+kd is. As a result, there are k bigger than m' and at most m such that a+kd is coprime with m'. But a+kd is bigger than m' and is coprime not just to m' but to the product of all primes in M. So it must have a prime factor outside of M. So A "contains" more primes than found in any finite set of prime factors.

Clear enough?

Answer 2

If $x,y,z$ are in arithmetic progression, then $x+z-2y=0$. By the S-unit theorem of Evertse, Schmidt and Schlikewei, this equation has only finitely many solutions in $x,y,z$ having all its prime factors in a fixed finite set (e.g. all primes at most $N$). So you can't have arbitrarily long arithmetic progressions of numbers of this form.

Answer 3

Here's an elementary proof that the length of an arithmetic progression is bounded in terms of $N$. Put $P= \prod_{p\le N} p$, and let $K$ denote the maximum difference between consecutive reduced residue classes $\pmod P$ (this is the Jacobsthal function). Clearly $K \le P$ (and of course much better bounds are known). Any $K$ consecutive numbers therefore contain one that is coprime to $P$.

Now we claim that any arithmetic progression of $N$-smooth numbers (all larger than $1$) has length at most $K$. Suppose $a+nq$ is such a progression with $a+nq$ being $N$-smooth for all $1\le n\le K$, and with all terms larger than $1$. First note that if $a$ and $q$ have a common factor $\ell$, then the arithmetic progression $a/\ell + nq/\ell$ also consists of $N$-smooth numbers. Thus we may assume that $a$ and $q$ are coprime.

Now suppose that $(q,P)= \ell$. Clearly the numbers $a+qn$ are all coprime to $\ell$ (since $(a,q)=1$). Choose $b$ such that $bq \equiv 1\pmod{P/\ell}$. Then the numbers $b(a+nq)$ when taken $\mod {P/\ell}$ constitute $K$ consecutive residue classes $\pmod{P/\ell}$ and therefore contain one residue class that is coprime to $P/\ell$. Therefore for some $1\le n\le K$ we have $(a+nq,P)=1$. This number $a+nq$ must have a prime factor larger than $N$.

Note: A small technicality was that we assumed that the elements in the progression were all larger than $1$. So there could be a progression of length $K$ if the progression starts with $1$.

Answer 4

This is a supplement to the elementary proofs given by The Masked Avenger and Lucia.

Theorem. For any $k$ there is $m$ such that no arithmetic progression of length $m$ is supported on $k$ distinct primes.

Proof. We prove by induction on $k$. For $k=0$ we can clearly take $m=2$. So let $k\geq 1$ and assume the statement for $k-1$ in place of $k$. That is, there is $m$ such that no arithmetic progression of length $m$ is supported on $k-1$ distinct primes. Consider an arithmetic progression of length $m'$ supported on the $k$ distinct primes $p_1,\dots,p_k$. Without loss of generality, the terms are coprime to the difference $d$. Observe that in any consecutive block of length $m$ in the progression, each prime $p_i$ occurs as a divisor by the induction hypothesis. Hence for $m'\geq m$ we get that $p_i\nmid d$, and for $m'\geq 2m$ we get that $p_i\mid kd$ for some $0<k<2m$. Combining the two statements, we infer that for $m'\geq 2m$ each $p_i$ is less than $2m$. Using Lucia's elementary argument, it follows that $m'<\prod_{p<2m}p<2^{4m}$. That is, for $m':=2^{4m}$ we get a contradiction, proving that no arithmetic progression of length $m'$ is supported on $k$ distinct primes.

Remarks (updated). The modern results on $S$-unit equations mentioned by Felipe Voloch yield an exponential bound on $m$. Lucia's argument combined with Iwaniec's bound on Jacobsthal's function yields directly $m\ll k^2(\log k)^2$, see Demonstratio Math. 11 (1978), 225–231. Weaker versions of this bound admit simple elementary proofs.