5 is prime. So are 5+6 (11), 5+2*6 (17), 5+3*6 (23), and 5+4*6 (29) — five prime in arithmetic progression. But 35 isn’t prime, and that’s obvious because it’s 5+5*6.

In general no arithmetic progression starting with prime *p* can have more than the first *p* entries prime.

But here’s another thing; consider 7+*k**6. For *k* = 0, 1, 2… you have 7, 13, 19, 25, 31, 37, 43, 49. The eighth entry is divisible by 7, of course, but also the fourth entry is divisible by 5. In fact the progression modulo 5 is 2, 3, 4, 0, 1, 2, 3, 4… Clearly one out of every five entries will be divisible by 5.

On the other hand consider 7+*k**30: 7, 37, 67, 97, 127, 157, 187, 217… None is divisible by 5, and in fact 7+*k**30 mod 5 = 7 mod 5 + (*k* mod 5) * (30 mod 5) = 2 + 0 = 2. Nor are any of the numbers in the progression divisible by 2 or 3 (or, by implication, 4 or 6) since 30 mod 2 = 30 mod 3 = 0. 187 is 11 * 17, so we only get six primes in this progression, but that’s more than we’d get with any common difference less than 30. (And more than 0, wise guy.)

Generally the progression *p* + *k* * *q* will contain a composite in its first *p*1 terms if *p*1 is a prime < *p* and *q* mod *p*1 ≠ 0.

So let’s say we want to find a progression of seven primes; what do we need? We need one of two things; either *p* = 7 and *q* mod *p1* = 0 for all primes through 5, or *p* > 7 and *q* mod *p1* = 0 for all primes through 7. That is, in the first case, *q* must be a multiple of 2*3*5 = 30. We’ve already seen 30 doesn’t work, but we can try multiples of 30, and we find *q* = 150 does work: 7, 157, 307, 457, 607, 757, 907 are all prime (and 1057 is a multiple of 7). For the second case *q* must be a multiple of 2*3*5*7 = 210, so we won’t find a progression with smaller common difference than 150.

In fact, in principle, with *q* a multiple of 210 we could get a progression of up to ten primes… though not eleven; 210 mod 11 = 1. But we don’t know which multiple of 210 we need, nor which starting prime *p *except that we need *p* mod 11 = 1 if we want to get ten primes.

Well, a little search program will turn it up. Use *p* = 199 and *q* = 210. That gives you, in fact, ten primes: 199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089. 2299 obviously is a multiple of 11.

With the first nine of these (or the last nine for that matter) we can get a prime magic square:

1669 | 199 | 1249 |

619 | 1039 | 1459 |

829 | 1879 | 409 |

This is the smallest magic square (in the sense of having the smallest magic constant) consisting of primes in arithmetic progression. (The smallest prime magic square, though, is

17 | 89 | 71 |

113 | 59 | 5 |

47 | 29 | 101 |

— see http://mathworld.wolfram.com/PrimeMagicSquare.html.)

The smallest common difference generating a progression of *k* primes is the *k*th element (starting with *k*=1) of: 0, 1, 2, 6, 6, 30, 150, 210, 210, 210… and the smallest corresponding *p*s are 2, 2, 3, 5, 5, 7, 7, 199, 199, 199… These are A033188 and A033189 in oeis.

Do the prime numbers contain arithmetic progressions of length *k* for all *k*? So it was conjectured for a long time, but the conjecture was not proven until 2004.

For more on this, see http://mathworld.wolfram.com/PrimeArithmeticProgression.html.