[Math] Using the Chinese Remainder theorem to solve the systems of congruence’s.

chinese remainder theorem

We got introduced to the Chinese Reminder Theorem, but I still haven't quite grasped it and I have a problem that asks:

Find $x \bmod 77$ if $x \equiv 2 \pmod 7$ and $x \equiv 4 \pmod {11}$.

My attempt was like so:
$$B = 7 * 77 * 11 = 5929$$
$$B_{1} = \frac{5929}{77} = 77$$
Using $B_{1}*x_{1} \equiv 1 \pmod {77}$:
$$77x_{1} \equiv 1 \pmod {77} $$
$$x_{1} \equiv 78 \pmod {77}$$
So then would the $x$ be $78$?

Best Answer

If $x\equiv 2\pmod 7$ then $x = 2+7k_1$ for some $k_1 \in \mathbb{Z}$. So substituting in your second equation you get $2+7k_1\equiv 4 \pmod {11}$, which gives you $k_1 \equiv 5\pmod{11}$, because $7^{-1}\equiv8\pmod{11}$. Hence $k_1 = 5+11k_2 $, for some $k_2 \in \mathbb{Z}$, and therefore $$x = 2+7(5+11k_2)=37+77k_2\equiv37\pmod{77} $$

Related Question