[Math] Using the Chinese Remainder Theorem to solve the following linear congruence: $17x \equiv 9 \pmod{276}$

Question

The book I am following (Elementary Number Theory by David Burton) uses the Chinese Remainder Theorem to solve $17x \equiv 9 \pmod{276}$ by breaking it up into a system of three linear congruences,
$$17x \equiv 9 \pmod{3}$$
$$17x \equiv 9 \pmod{4}$$
$$17x \equiv 9 \pmod{23}$$
I realize that the latter system is guaranteed to have a unique solution modulo $3 \times4\times23 = 276$. What I fail to understand is how and why the solution of this system of congruences the same as the solution of the initial congruence, $17x \equiv 9 \pmod{276}$. How can I solve this linear congruence using the Chinese Remainder Theorem?

Answer 1

First Bit - why the solution of the system is a valid answer

If we have a number $y$ such that $y\equiv9\pmod{3}$ and $y\equiv9\pmod{4}$ and $y\equiv9\pmod{23}$ then we know that $y-9\equiv0\pmod{3}$ and $y-9\equiv0\pmod{4}$ and $y-9\equiv0\pmod{23}$. In other words $y-9$ divides by $3$, $4$ and $23$. As these are all coprime then $y-9$ must divide by their product which is $276$.

Second Bit - actually doing the math

$17x\equiv9\pmod{3}$

$17x\equiv0\pmod{3}$

So $x=3y,y\in\mathbb{Z}$

So the second equation becomes

$17x\equiv9\pmod{4}$

$51y\equiv1\pmod{4}$

$3y\equiv1\pmod{4}$

$y\equiv3\pmod{4}$

So $y=4z+3,z\in\mathbb{Z}$

Putting this into the third equation:

$17x\equiv9\pmod{23}$

$51y\equiv9\pmod{23}$

$5y\equiv9\pmod{23}$

$5(4z+3)\equiv9\pmod{23}$

$20z+15\equiv9\pmod{23}$

$20z+6\equiv0\pmod{23}$

This leads easily to $z=2$ which then gives $y=11$ and hence $x=33$.

Checking: $17\times33=561=2\times276+9$