1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Dirk Jul 30 '18 at 12:55
2
$\begingroup$

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.

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