In mathematics, a covering system is a collection

$\backslash \{a\_1(\backslash mathrm\{mod\}\backslash \; \{n\_1\}),\backslash \; \backslash ldots,\backslash \; a\_k(\backslash mathrm\{mod\}\backslash \; \{n\_k\})\backslash \}$

of finitely many residue classes whose union covers all integers.

The notion of covering system was introduced by Paul Erdős in the early 1930s.

For example:

$\backslash \{0(\backslash mathrm\{mod\}\backslash \; \{3\}),\backslash \; 1(\backslash mathrm\{mod\}\backslash \; \{3\}),\backslash \; 2(\backslash mathrm\{mod\}\backslash \; \{3\})\backslash \},$

and

$\backslash \{1(\backslash mathrm\{mod\}\backslash \; \{2\}),\backslash \; 2(\backslash mathrm\{mod\}\backslash \; \{4\}),\backslash \; 4(\backslash mathrm\{mod\}\backslash \; \{8\}),\backslash \; 0(\backslash mathrm\{mod\}\backslash \; \{8\})\backslash \},$

and

$\backslash \{0(\backslash mathrm\{mod\}\backslash \; \{2\}),\backslash \; 0(\backslash mathrm\{mod\}\backslash \; \{3\}),\backslash \; 1(\backslash mathrm\{mod\}\backslash \; \{4\}),$

\ 5(\mathrm{mod}\ {6}),\ 7(\mathrm{mod}\ {12}) \}.

A covering system is called disjoint (or exact) if no two members overlap.

A covering system is called distinct (or incongruent) if all the moduli are different (and bigger than 1).

A covering system is called irredundant (or regular) if all the moduli are required to cover the integers.

The first two examples are disjoint.

The third example is distinct.

Some Unsolved problems

The following problem from Paul Erdős is unsolved: Whether for any arbitrarily large N there exists an incongruent covering system the minimum of whose moduli is at least N? It is easy to construct examples where the minimum of the moduli in such a system is 2, or 3 (Erdős gave an example where the moduli are in the set of the divisors of 120 ); D. Swift gave an example where the minimum of the moduli is 4 (and the moduli are in the set of the divisors of 2880). S. L. G. Choi proved that it is possible to give an example for N=20.

In another problem we want that all of the moduli (of an incongruent covering system) be odd. There is a famous unsolved conjecture from Erdős and Selfridge: an incongruent covering system (with the minimum modulus greater than 1) whose moduli are odd, does not exist ^* .

See also

---

• Chinese remainder theorem
• Residue number system

Number theory | Lefedőrendszer