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$

Answer 2

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

Answer 3

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