If $0<q<2000$, then at most $10$ consecutive terms of the arithmetic progression $a,\; a+q,\; a+2q\dots$ can be primes

Question

Show that if $0<q<2000$, then at most $10$ consecutive terms of the arithmetic progression $$a,\; a+q,\; a+2q\dots$$ can be primes.

If not, then there is an $r$ such that $$a+rq,\; a+(r+1)q,\; \dots ,\; a+(r+10)q$$ are all primes.

At this point, it seems like there should be a pigeonhole type argument that will kill the problem. But, I can't figure out how.

Answer 1

I assume that $a,\geq 2, r\geq 0$ and I prove the contrapositive. Suppose more than $10$, i.e. at least $11$ consecutive terms of the arithmetic progression $$a,\; a+q,\; a+2q\dots$$ are primes.

That is,

$$a+rq,\; a+(r+1)q,\; \dots ,\; a+(r+10)q$$ are all primes for some $a\geq 2,r\geq 0.$

Firstly, $q\neq 1,$ else one of $\{ a+rq, a+(r+1)q, \ldots, a+(r+n)q \}\ $ would be even and $>2,$ a contradiction. So $q>1.$

If $q$ is not a multiple of $2,$ then since $q>1\ $ and $\ q \neq 2k,\ $ it follows that $q$ is a multiple of some odd number $\geq 3.$ But since then $a\geq 2,\ r\geq 0\ $ and $q\geq 2,\ a+(r+1)q\geq 5 >2, \ $ and so either of $\ a+(r+1)q\ $ or $ a+(r+2)q\ $ is even, a contradiction. Thus $q$ is a multiple of $2.$

Since $a\geq 2,\ r\geq 0,\ $ and $\ q\geq 2,\ $ if follows that $\ a+(r+1)q\geq 4>3.\ $ If $q$ is not a multiple of $3,$ then one of $\ a+(r+1)q,\ a+(r+2)q\ $ or $\ a+(r+2)q\ $ is $>3$ and a multiple of $3,$ a contradiction. Thus $q$ is a multiple of $3.\ q$ is also a multiple of $2,$ so it is a multiple of $6.$

Since $a\geq 2,\ r\geq 0, q\geq 6,\ a+(r+1)q\geq 8>5.\ $ If $q$ is not a multiple of $5,$ then one of $\ a+(r+1)q,\ a+(r+2)q\ ,\ a+(r+3)q\ ,\ a+(r+4)q\ ,\ a+(r+5)q\ $ is $>5$ and a multiple of $5,$ a contradiction. Thus $q$ is a multiple of $5.\ q$ is also a multiple of $6,$ so it is a multiple of $30.$

A similar argument applies to $q$ being a multiple of $7,$ and so we see that $q$ is a multiple of $210.$

Now we consider two cases separately: $a\neq 11,\ $ and $a=11.$

If $a\neq 11,\ $ then one of $\{ a, a+rq, a+(r+1)q, \ldots, a+(r+10)q \}\ $ is $>11$ and divisible by $11,$ a contradiction.

If $a=11,$ then since $\ q\in\{ 210k:k\in\mathbb{N} \},\ $ we check each case individually.

$q=210$ fails because $231 = 13\times 17.$

$q=420$ fails for the same reason as $q=840:$ because $ 11 + 210\times 4 = 852 = 34 \times 37.$

$q= 630$ fails for the same reason as $q=1260: $ because $11 + 630 \times 2 = 1271 = 31\times 41.$

$q = 1050$ fails because $11 + 1050\times 3 = 3161 = 29\times 109.$

$q = 1470$ fails because $11 + 1470\times 2 = 2951 = 13\times 227.$

$q = 1680$ fails because $11 + 1680\times 1 = 1691 = 19\times 89.$

$q = 1890$ fails because $11 + 1890\times 2 = 3791 = 17\times 223.$

Therefore $q$ is a multiple of $210$ and $q > 1890.$ Therefore $q > 2000.$

Answer 2

Claim 1: There exists a prime $p\leq 11$ with $\gcd(p,q)=1.$

Claim 2: If $\gcd(b,c)=1,$ then there exists an $i$ such that $0\leq i< b$ such that $a+ic$ is divisible by $b.$

---

So one of $a,a+q,a+2q,\dots,a+(p-1)q$ is divisible by $p.$

In particular, if $p\leq 5,$ then two of the first $11$ must be divisible by $p,$ and thus are not equal, so one must must be non-prime.

Now you need to deal with the case where $p=7$ or $p=11.$ You have to eliminate the cases that start with $p.$

It might be a little more work if you need to prove the case when $a$ is negative.

Answer 3

If $q$ is odd then one of $a$ or $a+q$ is even. We might have $a = 2$, but three consecutive numbers cannot be primes. So $q$ must be divisible by $2$, and $a \ge 3$.

If $q$ is not divisible by $3$, then one of $a$, $a+q$, and $a+2q$ is. The first one might be 3, but four consecutive numbers cannot be primes. So $q$ must be divisible by $6$, and $a \ge 5$.

If $q$ is not divisible by $5$ or $7$, then the same argument shows that eight numbers in progression cannot be all primes, so $q$ is divisible by $210$ and $a \ge 11$.

One of $11$ consecutive numbers will be divisible by $11$ unless $q$ is divisible by $11$, which is not possible for $q < 2310$. They can all be primes if $a = 11$, so you check manually whether the values $11 + k\times 210$, $11+k\times 420$, $\dots$, $11+k\times 2100$ are all primes. For example, two out of the numbers $11 + k\times 2100$ for $0 \le k \le 10$ are composite, but this is (kind of) coincidence.

If you asked the same question with more than $12$ primes with $q \le 30,000$ or more than $16$ primes with $q <= 500,000$, the answer might be different.

But actually, for $q = 1,536,160,080$ and $q = 4,911,773,580$ there are $11$ primes $11 + k\times q$, $0 \le k \le 10$, in arithmetic progression. There are many more $q$, and they are rather quick to find even with trial division, if you don't check whether $11+q$ is a prime, then $11+2q$ is a prime etc., but whether any of $11+q$ to $11+10\times q$ is divisible by $13$, then by $17$, then by $19$ and so on.