MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Your proof, based on Dirichlet's theorem, only shows that no infinite arithmetic progression exists with all the terms supported on primes at most $N$. This statement has a simpler proof by noting that the reciprocal sum of any infinite arithmetic progression diverges, while the reciprocal sum of the numbers supported on primes at most $N$ equals $\prod_{p\leq N}(1-1/p)^{-1}$. I don't see how to extend these proofs from infinite arithmetic progressions to arbitrary long ones. – GH from MO Jun 22 '14 at 22:56
I think that Felipe Voloch's answer is the only correct argument so far that settles the original question. A good reference for the underlying Siegel-Mahler theorem is Lang's paper available at (see top of page 28 there). – GH from MO Jun 22 '14 at 23:35
Now we have two more elementary arguments, one by The Masked Avenger, and a more explicit version by Lucia. – GH from MO Jun 23 '14 at 8:41
I just gave an elementary argument (a supplement to the ones given already) that for any $k$ there is $m$ such that no arithmetic progression of length $m$ is supported on $k$ distinct primes. – GH from MO Jun 23 '14 at 10:11
In fact Lucia's argument combined with Iwaniec's bound on Jacobsthal's function yields $m\ll k^2(\log k)^2$. Thanks to Lucia and The Masked Avenger for their arguments and comments! – GH from MO Jun 23 '14 at 18:07
up vote 13 down vote accepted

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?

share|cite|improve this answer
Thanks this one is nice. And thanks to the other post I got to know about the nice theorem by Evertse, Schmidt and Schlikewei. +1. – shadow10 Jun 22 '14 at 16:11
I made it simple by ignoring the character of d. But if d has all the primes below p as factors, then one of the first (two or three) terms has a prime factor about as big as p or bigger anyway, so a positive progression of length n should have a term divisible by a prime q at least as big as p, which is the largest prime less than n. – The Masked Avenger Jun 22 '14 at 16:17
For any arithmetic progression $a,a+d,\dots,a+(m-1)d$ supported on primes at most $N$, you prove that its length $m$ is less than $p$, where $p>N$ is the smallest prime not dividing $d$. How do we get a uniform bound (depending only on $N$) from here? I could not follow your comment above. – GH from MO Jun 22 '14 at 23:04
@GHfromMO, noted. I hope the edit to follow satisfies you. – The Masked Avenger Jun 23 '14 at 5:40
Thanks for the clarification! – GH from MO Jun 23 '14 at 8:35

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.

share|cite|improve this answer
Hi, could you cite me a reference for "S-unit theorem of Evertse, Schmidt and Schlikewei", I can't find it on the web. Thanks a lot. – shadow10 Jun 22 '14 at 15:41
Actually, the Evertse, Schmidt and Schlikewei result is not needed and an older result of Siegel and Mahler is enough.… – Felipe Voloch Jun 22 '14 at 15:48

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

share|cite|improve this answer
This is a more technical version of what I hoped to convey (which I did not see until after editing my answer). This should convince @GHfromMO if my words do not. – The Masked Avenger Jun 23 '14 at 6:17
Nice explicit argument. – GH from MO Jun 23 '14 at 8:40
@Lucia could you emphasize a bit on Jacobsthal Function? I searched for it and got which defines it somehow differently, I think. Could you please clarify? And I also don't see how $K\ge P$ is obvious. Thanks a lot. – shadow10 Jun 23 '14 at 12:40
@shadow10: The OEIS article gives the right function. The bound $K\le P$ follows simply because any interval of $P$ integers contains $\phi(P)$ integers coprime to $P$. – Lucia Jun 23 '14 at 12:48
@shadow10 , searching for Jacobsthal's function on MathOverflow gives a number of hits as well as references to some recent contributions, epecially Thomas Hagedorn's paper in 2009. – The Masked Avenger Jun 23 '14 at 17:42

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.

share|cite|improve this answer
That's a nice extension. Let me note here that my argument gives the bound of $J(n)$ (the Jacobsthal function) for the length of a progression of integers composed only of primes dividing $n$. Now we recall that the Jacobsthal function can be bounded just in terms of $\omega(n)$ (this was Jacobsthal's result, and the best known is Iwaniec's bound of $\omega(n)^{2+o(1)}$. In other words the length of the progression is at most $k^{2+o(1)}$. – Lucia Jun 23 '14 at 13:13
@Lucia: I use induction on the existence of $m=m(k)$. My crude argument, based on $J(n)\leq n$, gives that $m(k)<16^{m(k-1)}$, i.e. $m(k)$ is bounded by a tower of height $k$. Your refinement $J(n)\leq\omega(n)^{2+o(1)}$ gives that $m(k)<m(k-1)^{2+o(1)}$, i.e. $m(k)$ is bounded by $2^{(2+o(1))^k}$. The mentioned results on $S$-unit equations yield an exponential bound. – GH from MO Jun 23 '14 at 14:32
But why not just use my proof. Doesn't it just give the Jacobsthal function as a bound? (And hence $k^{2+o(1)}$ as a uniform bound.) – Lucia Jun 23 '14 at 14:36
The arithmetic progression -1,0,1 suggests m=4 for k=0, or at least 3 if 0 is excluded/supports every prime. I like this inductive perspective. – The Masked Avenger Jun 23 '14 at 15:46
@GHfromMO: See for example this paper by H. Stevens:… – Lucia Jun 23 '14 at 16:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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