Originally Posted by

**Opalg** There may be more systematic ways of doing it, but here's how I would go about it.

We want to solve the congruences $\displaystyle \begin{cases}x & \equiv 7\!\!\pmod{17} \\ x& \equiv 9\!\! \pmod{13}\end{cases}$. That means that x is a multiple of 17, plus 7; and a multiple of 13, plus 9. Therefore $\displaystyle x = 17p+7=13q+9$ (for some integers p and q), from which $\displaystyle 13q-17p = 7-9=-2$.

But we know that 13*4 - 17*3=1. Multiply that by -2 to get 13*(-8) - 17*(-6)=-2. Therefore one solution for p and q is q=-8, p=-6. The corresponding value of x is x=-95 (=13*(-8)+9). However, we can add any multiple of 13*17=221 to that, and get another solution for x. It's usually convenient to work with the smallest positive solution, so we'll take x=-95+221=126.

To complete the solution, we need to solve the congruences $\displaystyle \begin{cases}x&\equiv 126 \!\! \pmod {221} \\ x&\equiv 3 \!\!\pmod {12}\end{cases}$. Use the same procedure here. The equations $\displaystyle x = 221p + 126 = 12q + 3$ tell us that $\displaystyle 221p - 12q = 3-126=-123$. But we know that 221*5 - 12*92 = 1. Multiply by -123 to get 221*(-615) - 12*(-11316) = -123. So we can take p=-615, giving x=221*(-615)+126=-135789. But we can adjust this by adding any multiple of 12*221=2652, so a better solution would be x=-135789+52*2652=2115.

That gives the answer you want: z = 2115 + 2652n.