Go back

Let’s take a look on some funny stuff about arithmetic progressions that envolve prime numbers in general.

First of all, some recaps and notations:

• A sequence \(a\) is a function \(a: \mathbb{N} \to \mathbb{R}\). And a subsequence of \(a\) is a restriction of its domain to an infinite set \(\mathbb{N}' \subset \mathbb{N}\).

• An arithmetic progression (AP) is a sequence \(a\) such that \(a_{n+1} = a_{n}+r, r \in \mathbb{R}\). It can also be written as \(a_{n+1} = A+nB, n \ge 0\), with \(A\) being \(a_{1}\) and \(B\) being \(r\). In this case, we will denote the set of all values of \(a_{n}\) as \(\{A+nB\}_{n \ge 0}\)

• We can also have finite sequences, if it is restricted to the finite set \(I_{n}\) where \(I_{n}=\{k \in \mathbb{N} \mid 1 \le k \le n\}\).

• Finally, we will denote the set of all prime numbers as \(\mathbb{P}\).

From now on, we’ll consider APs with \(A, B\) and its values in \(\mathbb{N}\), since we’re addresing APs that have prime values.

The first thing to note is that \(\mathbb{P} \setminus \{2n+1\}_{n \ge 0} = \{2\}\), since no prime can be even, except for \(2\). So the sequence of all primes is, in fact, a subsequence of \(a_{n+1} = 2n+1, n \ge 0\).

Another cool thing: if we consider \({an+b}_{n \ge 0}\) with \(qcd(a, b)>1\), this means that there is some \(m\) that divides \(a\) and \(b\), so it divides \(an+b\), so if \(m\) is not prime, \(an+b\) is not also. In fact, the only case where \(an+b\) is prime is when \(m\) is prime, so there is one prime at most in \({an+b}_{n \ge 0}\).

At this point you may ask: “Could there be an AP (non-constant) that only have primes?” The answer is no.

Assume that there is such a sequence \(a\). So \(a_{1} = p\) is prime and every \(a_{n+1} = a_{1}+(n-1)r = p+(n-1)r\), for some \(r \in \mathbb{N}\).
So if we take \(a_{p+1}\), we’ll get \(a_{p+1} = p+(p+1-1)r = p+pr = p(1+r)\), so \(a_{1} = p \mid a_{p+1}\). Contradiction, since \(a_{p+1} > a_{1}\) and \(a_{p+1}\) is supposed to be prime.

Now moving to something more interesting, let’s go back to our \(\{2n+1\}_{n \ge 0}\) set. As we saw, it contains an infinite amount of primes. Let’s test this for some other AP, like \(a_{n+1} = 4n+3, n \ge 0\), where \(a_{1}\), \(a_{2}\), and \(a_{3}\) are examples of primes.

We start by assuming that \(\{4n+3\}_{n \ge 0} \bigcap \mathbb{P} = \{p_{i}\}, i \in I_{k}\) for some \(k \in \mathbb{N}\). In other words, we assume the set of all prime terms of our sequence to be finite, aiming for contradiction.

Lemma 1: We have that \((4a+1)(4b+1) = 16ab+4a+4b+1 =\) \(4(4ab+a+b)+1\), so \((4a+1)(4b+1)\) has also the form \(4c+1\) for some \(c\).

Let K be the product of all \(p_{i}\)’s in our set. So let’s take \(\lambda = 4K-1 = 4(K-1)+3\). Since \(\lambda>1\), it has an unique prime decomposition, so \(\lambda = \prod\limits_{i=1}^{m}q_{i}\), where \(q_{i} \in \mathbb{P}\), for some \(m \in \mathbb{N}\).

Since \(\lambda\) is in the form \(4N+3\), some \(q_{j}\) is in the form \(4N+3\), because if \(q_{i}\) were in the form \(4N+1, \forall i \in I_{m}\), then \(\lambda\) would be in the form \(4N+1\) too (Lemma 1). So this \(q_{j} \in \{p_{i}\}\).

In fact, \(q_{j} \mid \lambda\) and \(q_{j} \mid K \implies q_{j} \mid 1\), contradiction (\(q_{j} \neq 1\)). So there is no \(k \in \mathbb{N}\) such that \(\{4n+3\}_{n \ge 0} \bigcap \mathbb{P} = \{p_{i}\}, i \in I_{k}\). In other words, \(\{4n+3\}_{n \ge 0}\) has infinite primes.

So, is there a way to generalize this fact and verify quickly whether an AP contains infinite primes or not? Indeed there is. My goal is not to show a formal proof of it, but to just show the theorem’s idea.

This theorem is called “Dirichlet’s theorem on arithmetic progressions”, and it states that if \(a\) and \(b\) are coprime, the set \(\{an+b\}_{n \ge 0}\) has infinite primes. It uses some Analytic Number Theory to do so, mainly trying to prove that the sum of the reciprocals of the primes in this set diverges.

The idea of this fact is, naively saying, connect the divergence of \(log\) to that sum using the Riemann Zeta function \(\zeta(s) = \prod\limits_{p \in \mathbb{P}} \frac{1}{1-p^{-s}}\).

We basically have that \(log(\zeta(s)) = \sum\limits_{p \in \mathbb{P}} -log(1-p^{-s})\) \(= \sum\limits_{p \in \mathbb{P}, n \in \mathbb{N}} \frac{p^{-ns}}{n} = \sum\limits_{p \in \mathbb{P}} \frac{1}{p^{s}} + O(1)\), with \(O(1)\) being some order 1 term. And indeed, \(\lim\limits_{s \to 1^{+}} log(\zeta(s)) = \infty\), which means that \(\mathbb{P}\) is infinite (Euclid’s Theorem).

Dirichlet extends this result with his “\(L\) function”, which uses an object called “Dirichlet’s character” to restrict the sum of prime reciprocals we got to some congruence class, obtaining \(\sum\limits_{p \in \mathbb{P} \bigcap \{an+b\}} \frac{1}{p^{s}} + O(1)\) from a function that envolves \(log(L(\chi, s))\), where \(\chi\) is the Dirichlet’s character.

Then the final idea is to prove that it diverges when \(s \to 1\), so that this set \(\{an+b\}_{n \ge 0}\) is infinite (see more about it).

As we saw, there is no infinite AP with only prime numbers, but of course there are finite ones, like \(\{6n+5\}_{n \in I_{5}}\) and \(\{30n+7\}_{n \in I_{6}}\).

It was proven by Ben Green and Terence Tao in 2004 that there are in fact finite APs containing only prime numbers with an arbitrary amount of terms, even though you can’t construct them using this theorem, but only prove their existence.

Currently, the largest finite AP containing only prime numbers known is \(\{155368778·23\#n+605185576317848261\}_{n \in I_{27}}\), where \(k\#\) is defined as the product of all primes up to \(k\). This sequence was found by the network computing project PrimeGrid in 2023.

Explaining its proof is pretty much out of reach for me, so you can read more about it here if you want.