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