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?


3 Answers 3


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



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

So the second equation becomes





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

Putting this into the third equation:







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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.