Proof That [x ≡ a1 mod m1 And x ≡ a2 mod m2] Has A Solution Iff (m1, m2)|(a1-a2)

Suppose there is an integer \(x\) such that \(x ≡ a_1 \bmod m_1\) and \(x ≡ a_2 \bmod m_2\). This means:

$$\begin{gather} x = km_1 + a_1 \\ km_1 + a_1 ≡ a_2 \bmod m_2 \\ km_1 + a_1 - a_2 = jm_2 \\ a_1 - a_2 = jm_2 -km_1 \end{gather}$$

Since \((m_1,m_2)\) divides both \(m_1\) and \(m_2\), then it should also divide \(a_1 - a_2\). The contrapositive is that if \((m_1,m_2) \nmid (a_1 - a_2)\), then the system of congruences does not have a solution.

Now assume that we don't know whether there is a solution but we do know that \((m_1,m_2) | (a_1 - a_2)\). This means \((m_1,m_2)n = a_1 - a_2 \). Since the \(\gcd\) can be written as a linear combination, then there are integers \(p\) and \(q\) such that \((m_1,m_2)=m_2 p - m_1 q\). This means \(m_2 pn - m_1 qn = a_1 - a_2 \) or:

$$\begin{gather} m_2 s - m_1 t = a_1 - a_2 \\ m_2 s +a_2 = m_1 t + a_1 \end{gather} $$

Let \(x=m_2 s +a_2\), then \(x=m_1 t + a_1\). Therefore:

$$\begin{gather} x ≡ a_2 \bmod m_2 \\ x ≡ a_1 \bmod m_1 \end{gather}$$

Thus we have shown that if \((m_1,m_2) | (a_1 - a_2)\), then the system of congruences has a solution.

Now suppose we have another solution \(y\):

$$\begin{gather} y ≡ a_2 \bmod m_2 \\ y ≡ a_1 \bmod m_1 \end{gather}$$

This means:

$$\begin{gather} x ≡ a_2 \bmod m_2 \wedge y ≡ a_2 \bmod m_2 \implies x-y ≡ a_2 - a_2 ≡ 0 \bmod m_2 \\ x ≡ a_1 \bmod m_1 \wedge y ≡ a_1 \bmod m_1 \implies x-y ≡ a_1 - a_1 ≡ 0 \bmod m_1 \end{gather} $$

If \(x-y\) is a common multiple of both \(m_1\) and \(m_2\), then it is a multiple of the lowest common mutiple:

$$ [m_1,m_2]|x-y $$

This means \(x ≡y \bmod [m_1, m_2]\). Therefore, the solution is unique modulo \([m_1,m_2]\).

Styles

(uses cookies)