Problem
NT-B2-M09-P011 Compatibility Criterion
Let \(m,n,a,b\) be integers with \(m,n>0\). Prove that \(x\equiv a\pmod m\), \(x\equiv b\pmod n\) has a solution if and only if \(\gcd(m,n)\mid a-b\).
For the converse, write \(x=a+mt\) and cancel the common divisor.
Let \(d=\gcd(m,n)\). If \(x\) is a solution, then \(m\mid x-a\), \(n\mid x-b\), so \(d\mid (x-a)\) and \(d\mid (x-b)\), hence \(d\mid a-b\). Conversely, suppose \(d\mid a-b\). Write \(m=dm_1\), \(n=dn_1\), \(\gcd(m_1,n_1)=1\). Seek \(x=a+mt\). We need \(a+d m_1t\equiv b\pmod {dn_1}\), or \(m_1t\equiv \frac{b-a}{d}\pmod {n_1}\). Since \(m_1\) is coprime to \(n_1\), it has an inverse, and such \(t\) can be chosen. Thus the system is solvable.
A theoretical problem inspired by the local collection; needed for rigorous work with non-coprime moduli.