4
$\begingroup$

For any $k>0$, prove that the arithmetic progression $ a, a+b, a+2b, a+3b, \dots$ where $\gcd(a,b)=1$ contains $k$ consecutive terms which are composite.

If it's for all $a,b$ then I'm confused. If we can set $a$ and $b$, we can set $a=(k+1)!$, $b=1$

  • 1
    What you say shows that IF you are allowed to choose $a$ and $b$, then you can get $k$ consecutive composite numbers, but what the problem is really asking you to do is to show that for ANY choice of $a$ and $b$, there will always be such a block of composite numbers.2012-06-29

2 Answers 2

7

You can show that for all $a$ and $b \neq 0$ with $\gcd(a,b) = 1$ and all $k > 0$ there are $k$ consective terms in the arithmetic progression $a,a+b,a+2b,\ldots$ that are composite. Let's see how to prove it. A sequence of $k$ consecutive terms has the form $a+xb, a+(x+1)b, \ldots, a+(x+k-1)b.$ We want to find an $x$ such that for each of the above terms $a+(x+i)b$ there is a prime $p_i$ that divides it. So we want to solve the system of simultaneous congruences \begin{align*} a+xb &\equiv 0 \pmod {p_0}\\ a+(x+1)b &\equiv 0 \pmod {p_1}\\ \vdots\\ a+(x+k-1)b &\equiv 0 \pmod {p_{k-1}} \end{align*} where the primes $p_i$ are still to be chosen. We would like to rewrite $a+(x+i)b \equiv 0 \pmod{p_i}$ as $x \equiv -\frac{a}{b}-i \pmod {p_i}$, so we want $b$ to have a multiplicative inverse modulo $p_i$. We can achieve this by choosing the $p_i$ in such a way that $b$ is coprime to $p_i$. Since there are only finitely many primes dividing $b$ but infinitely many primes in total, we can always find $k$ different primes $p_0,\ldots,p_{k-1}$ such that $b$ is invertible modulo $p_i$. So our system of congruences now looks like this \begin{align*} x &\equiv -a/b \pmod {p_0}\\ x &\equiv -a/b-1 \pmod {p_1}\\ \vdots\\ x &\equiv -a/b-(k-1) \pmod {p_{k-1}} \end{align*} (where the division by $b$ is allowed modulo $p_i$). Now you should be able to recognize which theorem you have to apply to get a solution. In fact you get infinitely many solutions! You have to choose $x$ large enough in order to ensure that not only $p_i$ divides $a+(x+i)b$ but also that it is a proper divisor.

  • 0
    You are right, I implicitly assumed $b \neq 0$. I added that assumption to my answer.2012-06-29
2

Assume $b\neq 0$. Let $n=\prod_{j=1}^{k}(a+jb)$. Consider $a+(n+1)b, \\ a+(n+2)b, \\ \vdots \\ a+(n+k)b.$ Then we have for any $i\in\{1, \dots , k\}$ that $\begin{align} a+(n+i)b &=(a+ib)+nb \\ &=(a+ib)+b\prod_{j=1}^{k}(a+jb) \\ &=\underbrace{(a+ib)}_{>1}\underbrace{\left[1+b \prod_{j=1,j\neq i}^{k}(a+jb) \right]}_{>1}. \end{align}$ Hence $a+(n+i)b$ is composite for each $i\in\{1, \dots , k\}$.