Problem
NT-B1-M08-P013 Compatibility Criterion
#13
★★★☆☆ Level 3 of 5
Prove that \(x\equiv a\pmod m\), \(x\equiv b\pmod n\) has a solution if and only if \(a\equiv b\pmod{\gcd(m,n)}\).
For necessity subtract the two congruences. For sufficiency reduce to a linear congruence.
Let \(d=\gcd(m,n)\). If a solution \(x\) exists, then \(x-a\) is divisible by \(m\), and \(x-b\) is divisible by \(n\), so both differences are divisible by \(d\). Hence \(a-b=(x-b)-(x-a)\) is divisible by \(d\).
Conversely, suppose \(d\mid a-b\). Look for \(x=a+mt\). We need \(a+mt\equiv b\pmod n\), i.e. \(mt\equiv b-a\pmod n\). This linear congruence is solvable because \(\gcd(m,n)=d\mid b-a\). Therefore the system has a solution.
This is the theoretical base for all non-coprime systems.