covering system

A covering system is a system of congruences such that every natural number $n$ is “covered” by at least one of the congruences, that is, given the finite sets $a$ and $m$ both containing $k$ nonnegative integers (but each $m_i>1$), for every $n$ there’s at least one value of $i$ such that $n\equiv a_{i}mod{m}_i$.

For example, Davenport gives the following system: $0mod2$, $0mod3$, $1mod4$, $1mod6$ and $11mod12$. For the sake of demonstration it will be sufficient here to show that this system of congruences covers all . Examining the congruences in the order stated for the first half of our sample range, the multiples of 2 and 3 are covered by the first two congruences, leaving us just 13, 17, 19 and 23 to worry about. The third congruence takes care of 13 and 17. The fourth congruence takes care of 19, with 13 already taken care of. The fifth congruence covers 23. In many cases, a particular number will be taken care of by more than one congruence. The following table shows all the congruences that cover the remainder of our sample range.

25	$1mod4$	$1mod6$
26	$0mod2$
27	$0mod3$
28	$0mod2$
29	$1mod4$
30	$0mod2$	$0mod3$
31	$1mod6$
32	$0mod2$
33	$0mod3$	$1mod4$
34	$0mod2$
35	$11mod12$
36	$0mod2$	$0mod3$

There are various open problems pertaining to covering systems. Erdős conjectured that for any positive $N$ there is always a covering system in which all the moduli are greater than $N$. Another one, posed by Erdős and Selfridge is whether there is a covering system in which all the moduli are odd. Erdős has presented a covering system which does not use 2 as a modulus but it does use 4.

Title	covering system
Canonical name	CoveringSystem
Date of creation	2013-03-22 18:04:37
Last modified on	2013-03-22 18:04:37
Owner	PrimeFan (13766)
Last modified by	PrimeFan (13766)
Numerical id	7
Author	PrimeFan (13766)
Entry type	Definition
Classification	msc 11B25