Find the multiplicative inverse of 219 modulo 910 using the Chinese Remainder Theorem.

Question

As $910= 7 \times 10 \times 13,$ I was able to come up with the following system of congruences:
$$2x\equiv 1\mod(7)$$
$$9x\equiv 1\mod(10)$$
$$11x\equiv 1\mod(13)$$
However, I am unsure as to how I should proceed with using the Chinese Remainder Theorem.

Answer 1

Observe that $2x \equiv 1\ (\text {mod}\ 7)$ is equivalent to $x \equiv 4\ (\text {mod}\ 7).$ Similarly $9x \equiv 1\ (\text {mod}\ 10)$ is equivalent to $x \equiv 9\ (\text {mod}\ 10)$ and $11x \equiv 1\ (\text {mod}\ 13)$ is equivalent to $x \equiv 6\ (\text {mod}\ 13).$ So you just need to solve the following system of congruences

$$x\equiv 4\ (\text {mod}\ 7)$$ $$x\equiv 9\ (\text {mod}\ 10)$$ $$x\equiv 6\ (\text {mod}\ 13)$$

Which is easy to solve using Chinese remainder theorem.

Let $N_1 = 10 \times 13 =130, N_2 =7 \times 13 =91$ and $N_3=7 \times 10= 70.$ Then $N_i$ and $n_i$ are relatively prime to each other for $i=1,2,3.$ So by Bezout's theorem $\exists$ integers $M_i$ and $m_i$ such that $$M_iN_i+m_in_i = 1$$ for $i=1,2,3,$ where $n_1=7,n_2=10,n_3=13.$ Now try to find $M_i$'s then the required solution is $\sum\limits_{i=1}^{3} a_iM_i N_i\ (\text {mod}\ N),$ where $N=7 \times 10 \times 13 = 910$ and $a_1=4,a_2=9,a_3=6.$

EDIT $:$ Here $M_1 = 2,M_2=1,M_3=-5.$ So the required solution of the above system of congruences is $$4 \times 2 \times 130 + 9 \times 1 \times 91 + 6 \times (-5) \times 70 = -241 \equiv 669 \ (\text {mod}\ 910).$$