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

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?

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

From the first congruence you have that $x \equiv 0$ ( mod 3). The second one gives us $x \equiv 1$ (mod 4 ) and the third one, by multiplying with -4 (mod 23 ) gives us that $x \equiv 10$ (mod 23) .

Now clearly the unique solution of the first two congruences is $x \equiv 9$ (mod 12)

So it remains to solve the system $$x \equiv 9 (mod 12)$$ $$x \equiv 10 (mod 23)$$

Let $M_{1}=23$ and $M_{2}=12$. We solve the congruences $$M_{1}y_{1} \equiv 1 (mod 12)$$ $$M_{2}y_{2} \equiv 1 (mod 23)$$

Take $y_{1}$ and $y_{2}$ to be the smallest positive integers satisfying this congruences.In our case we obtain $y_{1}=11$ and $y_{2}=2$. Then the solution of the original system of congruences is $$x \equiv 9M_{1}y_{1}+10M_{2}y_{2} (mod 276)$$

After computation, we obtain $$x \equiv 33( mod 276)$$

This is because the canonical map $\;\mathbf Z/276\mathbf Z\to\mathbf Z/3\mathbf Z\times\mathbf Z/4\mathbf Z\times\mathbf Z/23\mathbf Z\;$ is an isomorphism.

To solve the congruence you solve each congruence separately. Then you find the solution progressively. If you find, say, $x\equiv a\mod 4$ and $x\equiv b\mod 23$, you find the solution modulo $4\times 23$ from a *Bézout's relation between $4$ and $23$. Here you obviously have $$6\times 4-23=1,$$ and in the general case, you have to use the extended Euclidean algorithm. From this relation, you obtain the solution $$x\equiv b\cdot6\times4-a\cdot2\mod 4\times23.$$ Then do the same operations with $3$ and $92$.