2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.