I am solving problems from an old exam (in topology, but I've translated the problem into more algebraic terms). The problem is the following:

Let $a+b\mathbb{Z}=\{z\in \mathbb{Z}\mid z = a+bk \text{ for some }k\in \mathbb{Z}\}$ where $a\in \mathbb{Z}$ and $b\in \mathbb{Z}-\{0\}$. Suppose we have a collection of such sets $\{a_i+b_i\mathbb{Z}\mid i \in \mathbb{N}\}$ satisfying:

$$\bigcup_{i \in \mathbb{N}}(a_i+b_i\mathbb{Z})=\mathbb{Z}$$

Show whether it is always possible to extract a finite $I\subset \mathbb{N}$ s.t.

$$\bigcup_{i \in I}(a_i+b_i\mathbb{Z})=\mathbb{Z}$$

Unfortunately, I seem to have forgotten a lot of my elementary algebra... Nevertheless, I have attempted something:

Let $\{p_k\}=\{2,3,5,\dots\}$ be the set of primes. We can construct: $$\left(\bigcup_{k\in \mathbb{N}}(0+p_k\mathbb{Z})\right)\cup (-1+\ell_1 \mathbb{Z})\cup (1+\ell_2\mathbb{Z})=\mathbb{Z}$$

for some appropriate non-negative integers $\ell_1,\ell_2$. We could for instance pick $\ell_1=\ell_2=5$. Suppose there is a finite sub-collection $\{0+p_{k_j}\}$, $j=1,\dots,n$ s.t.

$$\left(\bigcup_{1\leq j\leq n}(0+p_{k_j}\mathbb{Z})\right)\cup (-1+5 \mathbb{Z})\cup (1+5\mathbb{Z})$$

Now, assume $p$ is some prime s.t. $p>\max\{p_{k_1},\dots,p_{k_n}\}$, then clearly $p\notin \bigcup_{1\leq j\leq n}(0+p_{k_j}\mathbb{Z})$. But here I run into a problem. I want $p\notin(-1+5 \mathbb{Z})\cup (1+5\mathbb{Z})$. That is, I want $5\nmid p-1$ and $5\nmid p+1$. This is of course possible if $p$ is a prime with a $7$ as its last digit. However, this approach means I have to prove that there are infinitely many primes ending on a $7$, which seems like a silly thing to prove for a simple problem like this. Surely, there is a nicer way of solving this?

EDIT: I am particularily interested in a solution not relying on topology, and whether a solution like my attempted solution works.


marked as duplicate by YuiTo Cheng, John Omielan, Yanior Weg, Lee David Chung Lin, Alexander Gruber May 11 at 5:27

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ It seems impossible, see here? $\endgroup$ – Dietrich Burde May 10 at 12:53
  • $\begingroup$ $\Bbb{Z} =2 \Bbb{Z} \cup (1 + 8 \Bbb{Z})\cup (-1 + 8 \Bbb{Z}) \bigcup_{p \text{ prime} \equiv 3,5 \bmod 8} p \Bbb{Z}$ $\endgroup$ – reuns May 10 at 13:03
  • $\begingroup$ @reuns Yes, that looks much nicer. Thanks:-) $\endgroup$ – KurtKnödel May 10 at 13:31
  • $\begingroup$ I'm guessing all the $b_i$ need be distinct less you fall into a complete residue system mod b ? $\endgroup$ – Roddy MacPhee May 10 at 15:17