3
$\begingroup$

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.

$\endgroup$
4
  • 5
    $\begingroup$ What happens if $\delta=a$? $\endgroup$
    – quasi
    Apr 17, 2018 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, 2018 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$ Apr 17, 2018 at 9:49
  • $\begingroup$ Would 3-5-7 or 7-37-67 be a case? $\endgroup$
    – usiro
    Apr 21, 2018 at 9:16

5 Answers 5

8
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ This post brought to you by the P.D.Q. Bernoulli Institute of Lower Mathematics. $\endgroup$
    – MJD
    Apr 17, 2018 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$ Apr 17, 2018 at 9:00
  • $\begingroup$ Is this an "insight" proof, is there a method to come up with this? $\endgroup$ Apr 17, 2018 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, 2018 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, 2018 at 6:53
3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ $f(nr+c)\equiv f(c) \bmod r$, taking $r=f(c)$ we get that $f(nf(c)+c)$ is divisible by $f(c)$ for all $n\in \Bbb{Z}$. $\endgroup$
    – reuns
    Jan 18, 2020 at 1:42
1
$\begingroup$

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


Update:

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.

$\endgroup$
4
  • $\begingroup$ "quasi-immediate" is funny! I didn't get it until just now. $\endgroup$
    – MJD
    Apr 19, 2018 at 13:02
  • $\begingroup$ @MJD: though you found a harder version of it. $\endgroup$
    – user65203
    Apr 19, 2018 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, 2018 at 13:15
  • $\begingroup$ @MJD: unintentional, I didn't get it either ! :) $\endgroup$
    – user65203
    Apr 19, 2018 at 13:27
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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!

$\endgroup$
3
  • 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, 2018 at 10:40
  • 1
    $\begingroup$ There is an arithmetric progression of length 26 known: en.wikipedia.org/wiki/… $\endgroup$ Apr 18, 2018 at 14:10
  • $\begingroup$ And 14933623 + 30030·n is prime for 13 terms (n=0..12). primerecords.dk/aprecords.htm#minimal $\endgroup$ Apr 18, 2018 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.