# Primes and arithmetic progressions

In a book on complex analysis, the authors prove:

Given finitely many (non-trivial) arithmetic progressions of natural numbers $$a_1, a_1+d_1, a_1+2d_1, \cdots$$ $$a_2, a_2+d_2, a_2+2d_2, \cdots,$$ $$a_k, a_k+d_k, a_k+2d_k, \cdots,$$ their totality (union) is never $\mathbb{N}$.

Given: any $k$ (non-trivial) arithmetic progressions.

Let $S$ denote the set of those numbers which are not in any of above $k$ arithmetic progressions.

If $S$ would have been finite, then we can form new finitely many arithmetic progressions which covers $S$, and combining them with given progressions, we will cover $\mathbb{N}$ by finitely many arithmetic progressions, a contradiction.

Thus $S$, the complement of all the given $k$ progressions, must be infinite.

Question Does $S$ contain infinitely many primes?

A non-trivial arithmetic progression means, the common difference is not $1$, i.e. it is not of the type $$a, a+1, a+2, \cdots$$

• Maybe one needs more conditions, see [Covering Systems.](en.wikipedia.org/wiki/Covering_system – André Nicolas Oct 30 '15 at 5:27
• Groups, you could add that the differences are distinct. @André Nicolas he's looking for a covering system that is also a partition. Indeed we can rephrase the question as follows: Given moduli $n_1,n_2,\ldots,n_k$, such that $\sum_{i=1}^{k}\frac{1}{n_i}=1$, does the set of numbers outside these congruence classes contain infinitely many primes? – Aravind Oct 30 '15 at 5:39
• Let $L$ be the LCM of the moduli, and let $S$ be the set of remainders modulo $L$ that are not covered. The answer to the question is YES if and only if $S$ contains $r$ such that $gcd(r,L)=1$. – Aravind Oct 30 '15 at 5:44
• I am sorry but with regard to the theorem, if we take sequences $0+3k$, $1+3k$ and $2+3k$ won't it just consist of all natural numbers? They are all non-trivial. – cr001 Oct 30 '15 at 5:49
• @cr001, the differences must all be distinct, as mentioned in the link. In your example, all are 3. – Aravind Oct 30 '15 at 5:50

Lemma: for a number $s\in S$, we can show $s+d_1d_2d_3...d_k$ is also in $S$.
Proof: Suppose $s'=s+d_1d_2d_3...d_k$ is not in $S$, then $s'$ is in one of the arithmetic sequence, say $s'=a_i+md_i$ for some $i$. Then we can express $s=a_i+(m-d_1d_2...d_{i-1}d_{i+1}...d_k)d_i$ and contradicts $s\in S$. QED.
Applying our lemma, we can find an arithmetic sequence in $S$ and the result follows from Dirchlet Thereom.
EDIT: This actually requires there exist an $s$ coprime with $d_1d_2...d_k$.
For example, if we let the finite arithmetic sequences be $2+3k$ and $1+6k$ then there won't be infinitely many primes in $S$ as $3$ is the only one.