Erdős Problem #947

Statement and convention.

There is no nontrivial finite exact covering of the integers by residue classes with distinct moduli. Here exact means that every integer belongs to exactly one class, and nontrivial means that all moduli exceed one. This convention matters: the single class $0\pmod1$ is a trivial exact cover. More generally, if a cover contains a modulus-one class, exactness forces it to be that singleton cover. We prove the classical Mirsky--Newman--Davenport--Rado result by a roots-of-unity argument.

An identity forced by exact coverage.

Suppose classes $a_i\pmod{n_i}$, $1\leq i\leq r$, give an exact cover. Normalize the representatives by $0\leq a_i<n_i$, and take $n_i\geq2$. The nonnegative integers in the $i$-th class are precisely $a_i+j n_i$, $j\geq0$. Thus, for every complex $z$ with $|z|<1$, absolute convergence and exact coverage give \[ \sum_{i=1}^r\frac{z^{a_i}}{1-z^{n_i}} =\sum_{m=0}^{\infty}z^m=\frac1{1-z}. \tag{1} \] The equality is an identity of rational functions. Indeed, after multiplying by the common denominator it becomes a polynomial equality on the open unit disk, and a polynomial vanishing at infinitely many points is identically zero.

The largest modulus cannot occur once.

Let $N=\max_i n_i$, and suppose only one class, say $a\pmod N$, has that modulus. Choose a primitive $N$-th root of unity $\zeta$. Because $N>1$, $\zeta\ne1$; and because every other $n_i<N$, $\zeta^{n_i}\ne1$. Multiply $1$ by $1-z^N$ and evaluate at $z=\zeta$. All terms except the one from modulus $N$ vanish. The right-hand side also vanishes, leaving \[ \zeta^a=0, \] which is impossible. The evaluation is legitimate after cancellation of the unique factor $1-z^N$; all remaining denominators are nonzero at $\zeta$.

Therefore every nontrivial finite exact cover repeats its largest modulus. In particular its moduli cannot all be distinct, proving the assertion.

An elementary finite-period version.

The same obstruction can be checked without infinite series. Let $L$ be the least common multiple of all moduli. Exact coverage of $\{0,\ldots,L-1\}$ gives the polynomial identity \[ \sum_i z^{a_i}\left(1+z^{n_i}+\cdots+z^{L-n_i}\right) =1+z+\cdots+z^{L-1}. \] At a primitive $N$-th root $\zeta$, every term with $n_i<N$ is a geometric sum equal to zero, since $N\mid L$ but $N\nmid n_i$. The unique modulus-$N$ term equals $(L/N)\zeta^a\ne0$, whereas the right-hand side is zero. This supplies a second, entirely finite proof of the same contradiction.

Sharpness of the repetition conclusion.

The two classes $0\pmod2$ and $1\pmod2$ form an exact cover, so repetition can indeed be the only obstruction in a simple example. More generally, take the classes \[ 2^{j-1}-1\pmod{2^j}\quad(1\leq j\leq s), \qquad 2^s-1\pmod{2^s}. \] They form an exact cover for every $s\geq1$. The first classes sort integers by the location of their first zero among the lowest $s$ binary digits; the last class consists of those whose lowest $s$ digits are all one. Thus one cannot replace the conclusion by a demand that every modulus repeat.

Attribution and assessment.

The nonexistence theorem was proved independently by Mirsky and Newman and by Davenport and Rado, as recorded at https://www.erdosproblems.com/947, checked 24 September 2026; the page cites Erdős's 1977 problem collection. The argument above reconstructs the classical roots-of-unity proof and includes its finite-period form. Only elementary polynomial and geometric-sum identities are used. The website's report of a Lean verification concerns the known theorem; no local Lean verification or novelty is claimed here.