covering system


A covering system is a system of congruencesMathworldPlanetmathPlanetmathPlanetmath such that every natural numberMathworldPlanetmath n is “covered” by at least one of the congruences, that is, given the finite setsMathworldPlanetmath a and m both containing k nonnegative integers (but each mi>1), for every n there’s at least one value of i such that naimodmi.

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 12<n<37. Examining the congruences in the order stated for the first half of our sample range, the multiplesMathworldPlanetmath 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 problemsPlanetmathPlanetmath 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 modulusMathworldPlanetmathPlanetmath but it does use 4.

References

  • 1 H. Davenport, The Higher Arithmetic, Sixth Edition. Cambridge: Cambridge University Press (1995): 57 - 58
  • 2 Paul Erdős & János Surányi Topics in the theory of numbers New York: Springer (2003): 46
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