Problem
NT-B2-M09-P015 Arbitrary Residues
#15
★★★★☆ Level 4 of 5
Let \(m_1,\ldots,m_k\) be pairwise coprime positive integers, and let \(r_1,\ldots,r_k\) be arbitrary integers. Prove that there exists an integer \(x\) such that \(x\equiv r_i\pmod {m_i}\) for all \(i\).
Use induction on the number of moduli.
For \(k=2\), this is the usual CRT. Suppose the statement is true for \(k-1\) moduli. The first \(k-1\) conditions are equivalent to one congruence \(x\equiv r\pmod M\), where \(M=m_1\cdots m_{k-1}\). Since \(m_k\) is coprime to each \(m_i\), \(\gcd(M,m_k)=1\). By CRT, \(x\equiv r\pmod M\), \(x\equiv r_k\pmod {m_k}\) is solvable. The induction is complete.
The general theorem is needed for stronger construction problems.