Solution to Simultaneous Linear Congruences

Theorem

Let:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a_1 x\)	\(\equiv\)	\(\displaystyle b_1\)	\(\displaystyle \)	\(\displaystyle \pmod {n_1}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a_2 x\)	\(\equiv\)	\(\displaystyle b_2\)	\(\displaystyle \)	\(\displaystyle \pmod {n_2}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\ldots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a_r x\)	\(\equiv\)	\(\displaystyle b_r\)	\(\displaystyle \)	\(\displaystyle \pmod {n_r}\)	\(\displaystyle \)

be a system of simultaneous linear congruences.

This system has a simultaneous solution iff:

$\forall i, j: 1 \le i, j \le r: \gcd \left\{{n_i, n_j}\right\}$ divides $b_j - b_i$.

If a solution exists then it is unique modulo $\operatorname{lcm} \left\{{n_1, n_2, \ldots, n_r}\right\}$.

Proof

We take the case where $r = 2$.

Suppose $x \in \Z$ satisfies both:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a_1 x\)	\(\equiv\)	\(\displaystyle b_1\)	\(\displaystyle \)	\(\displaystyle \pmod {n_1}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle a_2 x\)	\(\equiv\)	\(\displaystyle b_2\)	\(\displaystyle \)	\(\displaystyle \pmod {n_2}\)	\(\displaystyle \)

That is, $\exists r, s \in \Z$ such that:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle x - b_1\)	\(=\)	\(\displaystyle n_1 r\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle x - b_2\)	\(=\)	\(\displaystyle n_2 r\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Eliminating $x$, we get:

$b_2 - b_1 = n_1 r - n_2 s$

The RHS is an integer combination of $n_1$ and $n_2$ and so is a multiple of $\gcd \left\{{n_1, n_2}\right\}$.

Thus $\gcd \left\{{n_1, n_2}\right\}$ divides $b_2 - b_1$, so this is a necessary condition for the system to have a solution.

To show sufficiency, we reverse the argument.

Suppose $\exists k \in \Z: b_2 - b_1 = k \gcd \left\{{n_1, n_2}\right\}$.

We know that $\exists u, v \in \Z: \gcd \left\{{n_1, n_2}\right\} = u n_1 + v n_2$ from Bézout's Identity.

Eliminating $\gcd \left\{{n_1, n_2}\right\}$, we have:

$b_1 + k u n_1 = b_2 - k v n_2$.

Then:

• $b_1 + k u n_1 = b_1 + \left({k u}\right) n_1 \equiv b_1 \pmod {n_1}$
• $b_1 + k u n_1 = b_2 + \left({k v}\right) n_2 \equiv b_2 \pmod {n_2}$

So $b_1 + k u n_1$ satisfies both congruences and so simultaneous solutions do exist.

Now to show uniqueness.

Suppose $x_1$ and $x_2$ are both solutions.

That is:

• $x_1 \equiv x_2 \equiv b_1 \pmod n_1$
• $x_1 \equiv x_2 \equiv b_2 \pmod n_2$

Then from Intersection of Congruence Classes Modulo m the result follows.

$\blacksquare$

The result for $r > 2$ follows by a tedious induction proof.