Problem 947

There is no exact covering system - that is, a finite collection of congruence classes $a_i\pmod{n_i}$ with distinct $n_i$ such that every integer satisfies exactly one of these congruence classes.

Source: erdosproblems.com/947

Number theory
Covering systems

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

PROVED (LEAN), the site's label: the curator credits the theorem to Mirsky and Newman and, independently, to Davenport and Rado, and the Lean mark refers to a third-party Lean 4 proof described under Formalization. The standing derives from the accepted claim on its claim page (Mirsky–Newman, 1952).

Er50: Erdős, Paul, On integers of the form $2^k+p$ and some related problems. Summa Brasil. Math. 2 (1950), 113-123. The paper that introduced covering systems; it does not state the theorem, which the formal-conjectures docstring says first appeared there; the site cites only [Er77c]. Library home: Erdős 1950.
Er52: Erdős, Paul, Egy kongruenciarendszerekről szóló problémáról (On a problem concerning systems of congruences). Mat. Lapok 3 (1952), 122-128. The first printing of the theorem and of Mirsky and Newman's proof (p. 126).
Er77c: Erdős, Paul, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976), Lecture Notes in Math. 626 (1977), 43-72.
Ne71: Newman, Morris, Roots of unity and covering sets. Math. Ann. 191 (1971), 279-282.

Problem 947

Status

Proof claims

Discussion