OFFSET
1,3
COMMENTS
A disjoint covering system (DCS) is a system of congruences of the form x == a_i (mod m_i) such that every integer lies in exactly one of the congruences. Here the "moduli" are the m_i. The DCS is "natural" if it can be obtained by starting with the congruence x == 0 (mod 1) and "splitting": choosing a congruence and replacing it by r congruence.
REFERENCES
S. Porubsky and J. Schönheim, Covering systems of Paul Erdös: past, present and future, in Paul Erdös and his Mathematics, Vol. I, Bolyai Society Mathematical Studies 11 (2002), 581-627.
LINKS
I. P. Goulden, Andrew Granville, L. Bruce Richmond, and J. Shallit, Natural exact covering systems and the reversion of the Möbius series, Ramanujan J. (2019) Vol. 50, 211-235.
I. P. Goulden, L. B. Richmond, and J. Shallit, Natural exact covering systems and the reversion of the Möbius series, arXiv:1711.04109 [math.NT], 2017-2018.
EXAMPLE
For n = 4 the 6 possible disjoint congruence systems are
(a) x == 1 (mod 2), x == 2 (mod 4), x == 0 (mod 8), x == 4 (mod 8)
(b) x == 1 (mod 2), x == 0 (mod 4), x == 2 (mod 8), x == 6 (mod 8)
(c) x == 1 (mod 2), x == 0 (mod 6), x == 2 (mod 6), x == 4 (mod 6)
(d) x == 0 (mod 2), x == 3 (mod 4), x == 1 (mod 8), x == 5 (mod 8)
(e) x == 0 (mod 2), x == 1 (mod 4), x == 3 (mod 8), x == 7 (mod 8)
(f) x == 0 (mod 2), x == 1 (mod 6), x == 3 (mod 6), x == 5 (mod 6)
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Jeffrey Shallit, Nov 03 2017
STATUS
approved