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

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

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