discrete mathematics - Solving systems of basic congruences

I'm having some difficulty with a problem and I was hoping I could find some help here.

We've been covering congruences in my Discrete Math class, and, while I understand what they mean, I can't seem to solve systems of congruences greater than 2 equations in size.

What I mean is, I can solve problems that look like this:

$x \equiv 4 \mod 5$

$x \equiv 7 \mod 8$

I understand that I can solve this by doing something along the lines of:

$x = 5k + 4$

$5k + 4 \equiv 7 \mod 8$

$5k \equiv 3 \mod 8$

$k = 7$

$x = 5*7 + 4$

therefore $x = 39$

But I can't seem to figure out how to expand this to three (or more) equations, like so:

$x \equiv 4 \mod 5$

$x \equiv 7 \mod 8$

$x \equiv 3 \mod 6$

Disclaimer: I made these numbers up and I'm assuming there's always an answer. If this system doesn't work, any example problem will do. I'm just confused about the process.

Thank you!

Answer

To construct an $x$ equal to $x_1 \mod m_1$, $x_2 \mod m_1$ and $x_3 \mod m_3$.

we would like some expression $x = A + B + C$ such that mod $m_1$ kills $B$ and $C$, mod $m_2$ kills $A$ and $C$ etc.. and gives the correct values ($x_1$, $x_2$, ..)

For the things to get killed in the right we we should have $x = m_2 m_3 A' + m_1 m_3 B' + m_1 m_2 C'$ so e.g. reduction mod $m_1$ gives $m_2 m_3 A'$ so we should set $A' = x_1 \cdot \text{inverse of (}m_2 m_3\text{) mod }m_1$ and similarly with the other two.