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: $0\\mod 2$ , $0\\mod 3$ , $1\\mod 4$ , $1\\mod 6$ and $11\\mod 12$ . 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 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.

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.

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

单词	CoveringSystem
释义	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: $0\\mod 2$ , $0\\mod 3$ , $1\\mod 4$ , $1\\mod 6$ and $11\\mod 12$ . 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 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. 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. 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
随便看	orders of elements in integral domain OrderStatistics order statistics OrderTopology order topology OrderValuation order valuation OrdinalArithmetic ordinal arithmetic OrdinalExponentiation ordinal exponentiation OrdinalNumber ordinal number Ordinal numbers OrdinalSpace ordinal space OrdinaryGeneratingFunctionForLinearRecursiveRelations ordinary generating function for linear recursive relations OrdinaryQuiverOfAnAlgebra ordinary quiver of an algebra OreCondition Ore condition OreDomain Ore domain OreNumber