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

Answer 2

You need to apply the extended Euclidean algorithm anyway to apply the CRT, so why not do it right away for a direct computation of $219^{-1} \pmod {910}$?

So $$ \begin{array}{rrr|r} 910 & 1 & 0 & - \\ 219 & 0 & 1 & 4 \\ 34 & 1 & -4 & 6 \\ 15 & -6 & 25 & 2 \\ 4 & 13 & -54 & 3 \\ 3 & -45 & 187 & 1 \\ 1 & 58 & -241 & &\\ \end{array} $$

where the final line tells us that

$$1 = 58\cdot 910+ (-241)\cdot 219$$

so that the inverse of $219$ becomes $-241\equiv 669 \pmod{910}$

pro: it's a lot faster; con: no practice with CRT.