Solution to Simultaneous Linear Congruences

It has been suggested that this page or section be merged into Chinese Remainder Theorem/General Result. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Mergeto}} from the code.

Theorem

Let:

\(\ds a_1 x\)

\(\equiv\)

\(\ds b_1\)

\(\ds \pmod {n_1}\)

\(\ds a_2 x\)

\(\equiv\)

\(\ds b_2\)

\(\ds \pmod {n_2}\)

\(\ds \)

\(\ldots\)

\(\ds \)

\(\ds a_r x\)

\(\equiv\)

\(\ds b_r\)

\(\ds \pmod {n_r}\)

be a system of simultaneous linear congruences.

This system has a simultaneous solution if and only if:

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

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

Proof

We take the case where $r = 2$.

Suppose $x \in \Z$ satisfies both:

\(\ds a_1 x\)

\(\equiv\)

\(\ds b_1\)

\(\ds \pmod {n_1}\)

\(\ds a_2 x\)

\(\equiv\)

\(\ds b_2\)

\(\ds \pmod {n_2}\)

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

\(\ds x - b_1\)

\(=\)

\(\ds n_1 r\)

\(\ds x - b_2\)

\(=\)

\(\ds n_2 r\)

Eliminating $x$, we get:

$b_2 - b_1 = n_1 r - n_2 s$

The right hand side 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 \set {n_1, n_2}$ 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 \set {n_1, n_2}$.

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

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

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

Then:

$b_1 + k u n_1 = b_1 + \paren {k u} n_1 \equiv b_1 \pmod {n_1}$

$b_1 + k u n_1 = b_2 + \paren {k v} 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 the result follows.

$\blacksquare$

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

This needs considerable tedious hard slog to complete it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Finish}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.