3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Maybe one needs more conditions, see [Covering Systems.](en.wikipedia.org/wiki/Covering_system $\endgroup$ – André Nicolas Oct 30 '15 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 '15 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 '15 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 '15 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 '15 at 5:50
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.