Skip to main content
2 of 2
Fixed grammar in the beginning of the second paragraph.
GH from MO
  • 105.2k
  • 8
  • 292
  • 398

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

Lucia
  • 43.7k
  • 6
  • 193
  • 218