No infinite arithmetic progression exists with prime numbers

Question

I am trying to prove there is no infinite arithmetic progression involving only prime numbers. (In other words, I want to prove that if $a, b \in \mathbb{N}$, then there exists some $n$ such that $a + bn$ is not prime).

My approach: I think that taking a prime $p$ that is coprime to $b$, and showing that it divides many terms in the sequence is a viable way to go about proving this, but I can't see a clear way to write/implement this idea. Any advice?

This post is very similar, but I don't understand the answer proof very well. I would prefer to use the method I described above, if possible.

Answer 1

There are arbitrarily long sequences of consecutive composites. The well known proof: look at $$ k!+2, k!+3, \ldots, k! + k . $$

So no arithmetic progression can contain only primes.

Answer 2

Clearly not true when $a=0$ [indeed, $bn$ is not prime for $n=4$] so let us assume that $a \not = 0$. We can assume that $b \not = 0$, so let $a,b \not = 0$ and assume WLOG that $b>0$. Then it suffices to find, for any integral $a,b \not = 0$; $b \ge 1$; an integer $n$ such that $a+bn$ is not prime. Let $p$ be a prime larger than both $a,b$. Then setting $k$ any integer at least $(2+|a|)$, pick $n > kp$ such that $bn \pmod p = -a$; as $(a,b)=(b,p)=1$ and $n \pmod p$ takes on all values $0,1,\ldots, p-1$ as $n$ takes on values $kp,kp+1, \ldots, kp+p-1$ there indeed exists such an $n$. Then $a+bn \pmod p = 0$ and yet $a+bn > p$, as $b \ge 1$ and $a+bn > a + (1\times (2+|a|)p)$. So $a+bn$ cannot be prime.

*If you aren't allowed to assume that the family of prime integers is infinite then you can say this: Let $p$ be a prime of the form $p=a+bn$; $p>a,b$; either there exists a $p \in \{a+bn; n \in \mathbb{N}\}$, or $a+bn; n \in \mathbb{N}$ is not an infinite family of primes after all, and we are already done.

**You can go through the above proof and note that for each such $k$, there is an $n \in \{kp,kp+1, \ldots, kp+p-1\}$ such that $p|(a+bn)$. In fact, if you rather, you can also just note via simple arithmetic the following: If $p|(a+bn)$ then $p|(a+b(n+p))$. So not only does $p$ divide "many" terms in the sequence $\{a+bn; n \in \mathbb{N}\}$, it divides one term to start, and then every $p$-th term there on after.

Answer 3

Consider the arithmetic progression $a+bn$ for $a>1$. Note that if we choose $a=1$ we can ignore the first term and restate the progression from the second term as $(n+1) + (b-1)n=a'+b'n$. So we can always consider that there is a progression with $a>1$

Next, note that if $\gcd (a,n)\ne 1$, then every term will be divisible by $\gcd (a,n)$, and hence not prime, so in order that the progression feature any primes (other than perhaps the first term), it must be the case that $\gcd (a,n)=1$.

Finally, take any divisor $d$ of $a$. As the multiplier $b$ runs through $1,2,3,\dots$, it will at some point perforce take on the value $d$, and multiples of $d$, call these instances $b_{kd}$. Plainly, $d\mid b_{kd}$. So in these instances it will be the case that $d\mid (a+b_{kd}n)$, which by having $d$ as a factor cannot be prime.

Ergo, there can be no arithmetic sequences that contain only primes.