Why does there not exist a particular finite set of congruences that forms a partition of the set of integers

Question

There is a paragragh that I saw in an article and could not really understand. The article is Covering Systems of Congruences, J. Fabrykowski and T. Smotzer, Mathematics Magazine Vol. 78, No. 3 (Jun., 2005), pp. 228-231, DOI: 10.2307/30044163. It starts by discussing problem 9 from the 2002 American Invitational Mathematics Examination (AIME):

PROBLEM. Harold, Tanya, and Ulysses paint a very long fence. Harold starts with the first picket and paints every $h$th picket; Tanya starts with the second picket and paints every $t$th picket; and Ulysses starts with the third picket and paints every $u$th picket. If every picket gets painted exactly once, find all possible triples $(h,t,u)$.

After presenting the solution, the article goes on to say:

One can generalize the AIME problem and ask whether there exists a finite set of congruences, with all moduli distinct and greater than or equal to $2$, that forms a partition of the set of integers. This turns out to be impossible. Relaxing the assumption about partitioning the integers, one can look for finite sets of congruences such that every integer belongs to at least one of them."

Can anyone help explain why the first part is impossible?

Answer 1

Unfortunately there are finite distinct covering systems. See the system below:

$0(3), 0(4), 0(5), 1(6), 1(8), 2(10), 11(12), 1(15), 14(20), 5(24), 8(30), 6(40), 58(60), 26(120) $

Answer 2

The answer is yes. There are several.

This question gives one example: Prove {0 mod 2, 0 mod 3, 1 mod 4, 1 mod 6, 11 mod 12} is a covering system

$0 \mod 2, 0 \mod 3, 1\mod 4, 1\mod 6, 11 \mod 12$.

This paper is all about them https://arxiv.org/pdf/1705.04372.pdf

Answer 3

This is far from a full answer, but it gives a taste of how strong the constraints are.

Suppose we have $k$ congruences of the form $x \equiv a_i \pmod {m_i}$ where the $m_i$ are distinct and greater than $1$, and $0 < a_i \le m_i$ is the smallest natural number covered by the congruence. Further suppose that we've chosen a minimum set of congruences: i.e. there is no solution with fewer than $k$ congruences.

Consider two distinct congruences $x \equiv a_i \pmod {m_i}$ and $x \equiv a_j \pmod {m_j}$. We require $a_i \not\equiv a_j \pmod {\gcd(m_i, m_j)}$ to avoid collisions. (This follows from the Chinese remainder theorem, and is necessary and sufficient for non-intersection). Note that this implies that $\gcd(m_i, m_j) > 1$, so no two moduli are coprime.

Since a congruence with modulus $m_i$ covers $\frac{1}{m_i}$ of the integers, we must have $$\sum_i \frac{1}{m_i} = 1$$ so we have a partition of unity in Egyptian fractions. Combined with non-intersection, this is necessary and sufficient to partition the natural numbers.

Lemma: no non-trivial proper subset of the congruences is reducible to a single congruence. Suppose that we had a set of congruences $x \equiv a_i \pmod{m_i}$ which partition $x \equiv \alpha \pmod\mu$. Then clearly $m_i \equiv 0 \pmod\mu$ and $a_i \equiv \alpha \pmod\mu$, and the congruences $x \equiv \frac{a_i - \alpha}\mu \pmod {\frac{m_i}\mu}$ partition the natural numbers. But we started from a proper subset of the congruences, so this contradicts the assumption that $k$ is minimum.

Corollary: there is no $c > 1$ which is a common factor of all of the moduli. (Proof: if there were, one proper subset of the congruences would be reducible to $x \equiv 1 \pmod c$ and another to $x \equiv 2 \pmod c$. Since they can't both consist of a single congruence with modulus $c$, one of them is non-trivial, contradicting the lemma).

Corollary: none of the moduli is a prime power, for then that prime must be a common factor of all the moduli.

Corollary: $k \ge 19$. (Proof: we have to sum the reciprocals of the first 19 non-prime-powers to exceed $1$. Of course, those 19 numbers don't satisfy the no-pair-coprime constraint, and the sum of their reciprocals isn't exactly unity...).