# constructing a covering system of congruences?

A family of residue classes $a_i (\mod n_i)$ with $2\leq n_1\leq\cdots\leq n_r$ is called a covering system of congruences if every integer belongs to at least one of the residue classes, that is, every integer satisfies at least one of the congruences $a_i (\mod n_i)$. The known examples are:

$0 (\mod 2),\ 0 (\mod 3),\ 1 (\mod 4),\ 5 (\mod 6),\ 7 (\mod 12)$

$0 (\mod 2),\ 0 (\mod 3),\ 1 (\mod 4),\ 3 (\mod 8),\ 7 (\mod 12),\ 23 (\mod 24)$

The proof of that the above families are each a covering system of integers are not difficult.

My question is the other side, i.e., that how can we construct a covering for integers from the given numbers for example $2,3$ with their multipliers as moduli?

• Sorry, I don't really understand your question. Could you maybe formulate the question and then, after that, make an example, not mixed up as it seems to be right now?
– Dirk
Jul 30 '18 at 12:55

Here's one way to construct those covers.

Every integer is $0\bmod2$ or $1\bmod2$. Keep one of those congruences, doesn't matter which one, say, $0\bmod2$, and go to work on the other one.

Every integer that's $1\bmod2$ is either $1\bmod4$ or $3\bmod4$. Keep $1\bmod4$, and go to work on $3\bmod4$ (as before, and as in all the following, we could have made a different choice).

If $n\equiv3\bmod4$, then $n\equiv3\bmod{12}$, or $n\equiv7\bmod{12}$, or $n\equiv11\bmod{12}$.

If $n\equiv3\bmod{12}$, then also $n\equiv0\bmod3$.

If $n\equiv11\bmod{12}$, then $n\equiv5\bmod6$.

So the integers are covered by $0\bmod2$, $0\bmod3$, $1\bmod4$, $5\bmod6$, and $7\bmod{12}$.

To get your other example, split the $3\bmod4$ into $3\bmod8$ and $7\bmod8$, then split one of those into 3 classes modulo 24, and cover one of those classes using the modulus 3, and another using modulus 12.