<s>[INST] System of congruences where $\gcd(m, n)\ne1$ I have to solve this system of congruences:
$$
\begin{cases}
x^2+2x+2\equiv 0\pmod{10}\\
7x\equiv 20\pmod{22}
\end{cases}
$$
after some calculations
$$
\begin{cases}
x\equiv 1\pmod{5}\\
x\equiv 2\pmod{5}\\
x\equiv 0\pmod{2}\\
x\equiv 6\pmod{2}\\
x\equiv 6\pmod{11}\\
\end{cases}
$$
since $x\equiv 6\pmod{2}$ and $x\equiv 0\pmod{2}\\$ are equal, we get:
$$
\begin{cases}
x\equiv 1\pmod{5}\\
x\equiv 2\pmod{5}\\
x\equiv 0\pmod{2}\\
x\equiv 6\pmod{11}\\
\end{cases}
$$
$$
\begin{cases}
x\equiv 1\pmod{5}\\
x\equiv 6\pmod{11}\\
\end{cases}\implies x\equiv 46\pmod{55}
$$
$$
\begin{cases}
x\equiv 0\pmod{2}\\
x\equiv 2\pmod{5}\\
\end{cases}\implies x\equiv 2\pmod{10}
$$
but, $\gcd(55,10)\ne1$, so I cannot apply the Chinese theorem. What have I done wrong?
 [/INST] \begin{cases}
x\equiv 0\;(mod\;2)\\
\hline
x\equiv 1\;(mod\;5)\\
x\equiv 2\;(mod\;5)\\
\hline
x\equiv 6\;(mod\;11)\\
\end{cases}
So you want a solution modulo $2 \cdot 5 \cdot 11 = 110$.
This is how I would solve it.
\begin{array}{r|rrr}
   & 2 & 5 & 11 \\
\hline
55 & 1 & 0 & 0\\
22 & 0 & 2 & 0\\
10 & 0 & 0 & -1 \\
\hline
\end{array}
Note that the top row is the three prime moduli that we are using.
The left column is 
   $\dfrac{2 \cdot 5 \cdot 11}{2} = 55 \quad $, 
   $\dfrac{2 \cdot 5 \cdot 11}{5} = 22 \quad$, and
   $\quad \dfrac{2 \cdot 5 \cdot 11}{11} = 10$.
The remaining entries show $55, 22, 10$ modulo $2, 5, 11$.
The goal is to multiply $55, 22$ and $10$ by the appropriate integers so that the three diagonal elements are all $1$.


*

*$55$ already gives us a diagonal element of $1$.

*Since $2 \cdot 3 \equiv 1 \pmod 5$, we change $22$ to $22 \cdot 3 = 66$.

*Since $-1 \cdot -1 \equiv 1 \pmod{11}$, we change $10$ to $10 \cdot (-1) = -10$.


\begin{array}{r|rrr}
   & 2 & 5 & 11 \\
\hline
55 & 1 & 0 & 0\\
22 & 0 & 2 & 0\\
10 & 0 & 0 & -1 \\
\hline
55 & 1 & 0 & 0\\
66 & 0 & 1 & 0\\
-10 & 0 & 0 & 1 \\
\hline
\end{array}
We use those numbers, $55, 66, -10$ as follows
$\left. \begin{align}
   x &\equiv 0 \pmod 2 \\
   x &\equiv 1 \pmod 5 \\
   x &\equiv 6 \pmod{11}
\end{align} \right\}
\iff x \equiv 0(55) + 1(66) + 6(-10) \equiv 6 \pmod{110}$
$\left. \begin{align}
   x &\equiv 0 \pmod 2 \\
   x &\equiv 2 \pmod 5 \\
   x &\equiv 6 \pmod{11}
\end{align} \right\}
\iff x \equiv 0(55) + 2(66) + 6(-10) \equiv 72 \pmod{110}$
</s>