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

1 Answer 1

Reset to default
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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .