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

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.

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

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.