Chinese remainder theorem for three equations?

Question

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.

Answer 1

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$.

Answer 2

You solve the first two, then take that result and the remaining equation and you solve those two.

Answer 3

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.