I conjecture that there does not exist an arithmetic sequence where every number is prime. Put another way, the set $$S_{a,b} = \{a + \delta b \ \vert \delta \in \mathbb{N}\}$$ Where $a, b \in \mathbb{N}$

contains some composite number.

I have no idea how to approach such a question. Googling let me to theorems about densities of primes in arithmetic sequences (Green-Tao and the like), but nothing that answers this elementary question.

  • 4
    $\begingroup$ What happens if $\delta=a$? $\endgroup$ – quasi Apr 17 '18 at 8:00
  • $\begingroup$ @quasi That takes care of $a≠1$ but if $a=1$ it's not always sufficient. Fortunately it's not hard to see that $b\delta+1$ contains arbitrarily large multiples of $b+1$. $\endgroup$ – MJD Apr 17 '18 at 8:32
  • $\begingroup$ If $a,b\in \Bbb N$ and $\gcd (a,b)=1$ then there are infinitely many $d\in \Bbb N$ such that $a+bd$ is prime. This is called Dirichlet's Theorem. It is not easy or elementary. $\endgroup$ – DanielWainfleet Apr 17 '18 at 9:49
  • $\begingroup$ Would 3-5-7 or 7-37-67 be a case? $\endgroup$ – usiro Apr 21 '18 at 9:16

As quasi points out in a comment, when $\delta=a$ the element is $a(b+1)$ which is composite unless possibly $a=1$.

More generally just take $\delta = kb+k+a$ for any $k$ whatever. Then the element is $$kb^2 +(k+a)b + a = (kb+a)(b+1)$$ which is composite.

  • 1
    $\begingroup$ This post brought to you by the P.D.Q. Bernoulli Institute of Lower Mathematics. $\endgroup$ – MJD Apr 17 '18 at 9:00
  • $\begingroup$ Much appreciated :) I came up with the $a(b + 1)$ right after posting the question, but didn't notice the corner case of $a = 1$. $\endgroup$ – Siddharth Bhat Apr 17 '18 at 9:00
  • $\begingroup$ Is this an "insight" proof, is there a method to come up with this? $\endgroup$ – Siddharth Bhat Apr 17 '18 at 9:01
  • $\begingroup$ Quasi's observation takes care of $a≠1$. For $a=1$ I just looked at an example, picking $4b+1$ arbitrarily. Because $\gcd(4,5)=1$ this was obviously going to hit a multiple of 5 every 5 terms. The generalization was immediate: $1+\delta b$ contains infinitely many multiples of $b+1$. $\endgroup$ – MJD Apr 17 '18 at 9:06
  • 1
    $\begingroup$ @siddharth I wrote up my thought process in more detail: blog.plover.com/math/arithmetic-sequences.html $\endgroup$ – MJD Apr 20 '18 at 6:53

I answered similar questions here and here.

"An Introduction To The Theory Of Numbers" by Hardy, Theorem 21, page 18.

THEOREM 21. No polynomial $f(n)$ with integral coefficients, not a constant, can be prime for all $n$, or for all sufficiently large $n$.

In this case $f(\delta)=a+\delta b$. It's a more powerful result, but the proof is very simple, as you will see.


This is quasi-immediate: $a+ab$ is composite.


There is a special case which invalidates the claim: $a=1$.

Using MJD's method, $a+(a+b+1)b=(a+b)(b+1)$ is always composite.

  • $\begingroup$ "quasi-immediate" is funny! I didn't get it until just now. $\endgroup$ – MJD Apr 19 '18 at 13:02
  • $\begingroup$ @MJD: though you found a harder version of it. $\endgroup$ – Yves Daoust Apr 19 '18 at 13:06
  • $\begingroup$ I meant your pun: it was in fact "quasi-immediate" because quasi had immediately posted a comment pointing it out. $\endgroup$ – MJD Apr 19 '18 at 13:15
  • $\begingroup$ @MJD: unintentional, I didn't get it either ! :) $\endgroup$ – Yves Daoust Apr 19 '18 at 13:27

We can in fact prove that the sequence contains infinitely many multiples of every number $n$ that is relatively prime to $b$. (Like $n = b + 1$ in MJD's answer.)

Pick any number $n$ such that $\gcd(b, n) = 1$. This means there exist integers $x, y$ such that $nx - by = 1$. (The nice thing about $n=b+1$ is that we can write down $x$ and $y$ explicitly, as $x=y=1$.)

Now take $\delta = nk + ay$ for any $k$.

Then, $a + \delta b = a + (nk + ay)b = a + nkb + a(nx - 1) = n(kb + ax)$ which is a multiple of $n$.


This is for your information:

There is an arithmetic progression which has ten prime terms and its first term is 199 and common difference is 210:

$199, 409, 829,1039,1249, 1459, 1669,1879, 2089$

Also due to Sierpinski theorem the longest Arithmetic progression with prime numbers has 13 terms, first number is $4943$ and the common difference is $60060$.

There is also a theorem that claims there is infinitely many Arithmetic progressions with 13 numbers and common difference $30030$ with all numbers prime, but there has not been found even one yet!

  • 1
    $\begingroup$ > "Also due to Sierpinski theorem the longest Arithmetic progression with prime numbers has 13 terms" But doesn't the Green-Tao theorem tell us that we can get arbitrarily long arithmetic progressions consisting entirely of prime numbers? $\endgroup$ – Dylan Apr 17 '18 at 10:40
  • 1
    $\begingroup$ There is an arithmetric progression of length 26 known: en.wikipedia.org/wiki/… $\endgroup$ – Michael Stocker Apr 18 '18 at 14:10
  • $\begingroup$ And 14933623 + 30030·n is prime for 13 terms (n=0..12). primerecords.dk/aprecords.htm#minimal $\endgroup$ – Michael Stocker Apr 18 '18 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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