Is there a straightforward approach for solving the Chinese Remainder Theorem with three congruences?
$$x \equiv a \bmod A$$
$$x \equiv b \bmod B$$
$$x \equiv c \bmod C$$
Assuming all values are positive integers, not necessarily prime, but sometimes solutions do exist.
$\endgroup$ 13 Answers
$\begingroup$You solve the first two, then take that result and the remaining equation and you solve those two.
$\endgroup$ 0 $\begingroup$For example, suppose you want $$ \eqalign{ x &\equiv 2 \mod 3 \cr x &\equiv 5 \mod 20\cr x &\equiv 1 \mod 7\cr} $$ From the first two, using the Euclidean algorithm, you get $x \equiv 5 \mod 60$. Then from this and the last equation, again using the Euclidean algorithm, $x \equiv 365 \mod 420$.
EDIT: For an example without a "clean inverse", by which I supppose you mean the moduli are not all coprime:
$$ \eqalign{ x &\equiv 5 \mod 15\cr x &\equiv 8 \mod 21\cr x &\equiv 15 \mod 35\cr}$$ From the first two, the Euclidean algorithm gives you $x \equiv 50 \mod 105$. Now $105$ is already divisible by $35$, and $50 \equiv 15 \mod 35$, so they are compatible: the final result is $x \equiv 50 \mod 105$.
EDIT: What I mean by applying the Euclidean algorithm is this. Consider the first two equations of the last set:
$x \equiv 5 \mod 15$, $x \equiv 8 \mod 21$. Write these as
$$x = 5 + 15 y = 8 + 21 z$$
so that $$15 y = 3 + 21 z$$
Since $21 = 15 + 6$, this becomes $15 (y - z) = 3 + 6 z$, or (with $w = y - z$) $$15 w = 3 + 6 z$$
Then $15 = 2\times 6 + 3$, we get $$v = z - 2 w,\ 3 w = 3 + 6 v$$
Now $6$ is divisible by $3$, and we can write
$$ w = 1 + 2 v $$
where $v$ is arbitrary. Now substitute back:
$$ \eqalign{z &= v + 2 w = 2 + 5 v\cr x &= 8 + 21 z = 50 + 105 v\cr}$$
i.e. $x \equiv 50 \mod 105$.
For $x$ modulo A and modulo BC, solving $y_1 \times A + z_1 \times BC = 1$ by the extended Euclidean algorithm gives $ x_1 = z_1 \times BC$.
For $x$ modulo B and AC, solving $y_2 \times B + z_2 \times AC = 1$ gives $ x_2 = z_2 \times AC$ .
Finally, for $x$ modulo C and AB, solving $y_3 \times C + z_3 \times AB = 1$ gives $x_3 = z_3 \times AB$. A solution is therefore $x_1 + x_2 + x_3 = x$. All other solutions are congruent to $x$ modulo ABC.
$\endgroup$
