Ytukyg

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?

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 notequiv 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 pmodmu$. Then clearly $m_i equiv 0 pmodmu$ and $a_i equiv alpha pmodmu$, 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...).

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) $

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, 1mod 4, 1mod 6, 11 mod 12$.

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