# Covering $\mathbb{Z}$ by arithmetic progressions [duplicate]

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

• $\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}$ – reuns May 10 at 13:03
• I'm guessing all the $b_i$ need be distinct less you fall into a complete residue system mod b ? – Roddy MacPhee May 10 at 15:17