Problem
NT-B1-M04-P021 Compatibility Criterion for Two Congruences
#21
★★★★☆ Level 4 of 5
Prove: the system \(x\equiv r\pmod m\), \(x\equiv s\pmod n\) has a solution if and only if \(r\equiv s\pmod{\gcd(m,n)}\).
Necessity follows from \(x-r\) being divisible by \(m\) and \(x-s\) by \(n\). For sufficiency, reduce to a linear congruence.
Let \(d=\gcd(m,n)\). If a solution \(x\) exists, then \(x-r\) is divisible by \(m\), and \(x-s\) is divisible by \(n\), so both are divisible by \(d\). Then \(r-s=(x-s)-(x-r)\) is divisible by \(d\).
Conversely, suppose \(d\mid r-s\). Look for \(x=r+mk\). We need \(r+mk\equiv s\pmod n\), i.e. \(mk\equiv s-r\pmod n\). This linear congruence has a solution exactly because \(\gcd(m,n)=d\mid s-r\). Hence the original system is compatible.
This is the main theoretical result for non-coprime moduli.