Using the Chinese Remainder theorem to solve the systems of congruence's.

Question

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

Answer 1

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

Answer 2

I don't know if this is what you have on your mind, but I would do it like this:

$x=7a+2$ and $x= 11b+4$ for some integers $a,b$ so $7a= 11b+2$ and thus $7|11b+2$. Multiply this with 2 and we get $7|22b+4$ so $7|b-3$. Now we can write $b=7t+3$ and thus $x=77t+37$. So $x \equiv 37 \pmod {77}$.

Answer 3

Let us use the Euclidean algorithm to express $\gcd(7,11)$ as a linear combination: $$4 = 11 - 7\\ 3 = 7 - 4 = 2 \cdot 7 - 11 \\ 1 = 4 - 3 = 2 \cdot 11 - 3 \cdot 7.$$ Now, $x = (2 \cdot 11 - 3 \cdot 7) x = 2 (11x) - 3 (7x)$. By the given congruences, $11x \equiv 11 \cdot 2 = 22 \pmod{77}$ and $7x \equiv 7 \cdot 4 = 28 \pmod{77}$. Therefore, $x \equiv 2 \cdot 22 - 3 \cdot 28 = -40 \equiv 37 \pmod{77}$.

(This is hopefully closer to what you were hinting at in your comments as the method of solving CRT problems that your source is using.)

Answer 4

You have to start from a Bézout's relation between $7$ and $11$: $$2\cdot 11-3\cdot7=1.$$ Then the solutions to a system of congruences $\;\begin{cases}x\equiv a\pmod 7\\x\equiv b\pmod{11}\end{cases}$ is $$x\equiv a\cdot 2\cdot 11-b\cdot 3\cdot 7\pmod{7\cdot 11}$$ Here you obtain $x\equiv 44-84=-40\pmod{77}$. The smallest positive integer staisfying this congruence is $-40+77=37$.

The present case is trivial, but the general method to find a Bézout's relation between two numbers is the extended Euclidean algorithm.

Answer 5

$\bmod 7\,\&\,11\!:\ 2x\equiv -3\iff \bmod 77\!:\ 2x\equiv -3\equiv 74\iff x\equiv 37$