The Chinese remainder theorem is a fundamental result in number theory that allows one to decompose congruence problems to into simpler ones. The theorem says the following.
Suppose that \(m_1,m_2\) are coprime natural numbers and \(a_1,a_2\) are integers. Then there is a unique integer \(x\) in the range \(0\leq x \leq m_1m_2-1\) such that \[x \equiv a_1 \pmod{m_1} \quad \text{ and } \quad x \equiv a_2 \pmod{m_2}.\] Prove the Chinese remainder theorem using the pigeonhole principle.
We have ten positive integers \(x_1,\dots,x_{10}\) such that \(10\leq x_i\leq 99\) for \(1\leq i\leq 10\). Prove that there are two disjoint subsets of \(x_1,\dots,x_{10}\) with equal sums of their elements.