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

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

Now clearly the unique solution of the first two congruences is $$x \equiv 9 \pmod{12}$$

So it remains to solve the system $$x \equiv 9 \pmod{12}$$ $$x \equiv 10 \pmod{23}$$

Let $$M_{1}=23$$ and $$M_{2}=12$$. We solve the congruences $$M_{1}y_{1} \equiv 1 \pmod{12}$$ $$M_{2}y_{2} \equiv 1 \pmod{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} \pmod{276}$$

After computation, we obtain $$x \equiv 33\pmod{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$.