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

  • 1
    $\begingroup$ Maybe one needs more conditions, see [Covering Systems.](en.wikipedia.org/wiki/Covering_system $\endgroup$ Oct 30, 2015 at 5:27
  • $\begingroup$ 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? $\endgroup$
    – Aravind
    Oct 30, 2015 at 5:39
  • $\begingroup$ 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$. $\endgroup$
    – Aravind
    Oct 30, 2015 at 5:44
  • $\begingroup$ 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. $\endgroup$
    – cr001
    Oct 30, 2015 at 5:49
  • $\begingroup$ @cr001, the differences must all be distinct, as mentioned in the link. In your example, all are 3. $\endgroup$
    – Aravind
    Oct 30, 2015 at 5:50

1 Answer 1


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.


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.