System of congruence relations

Question

Solve the system of congruence relations:

$2x+3y\equiv 1\pmod {11}$

$x+4y\equiv 4\pmod {11}$

Could someone give a hint how to solve this system.

I know that Chinese remainder theorem can't be used because modulo numbers ($11$) are not relatively prime.

Answer 1

Write your system in matrix form: $\left( \begin{matrix} 2 & 3 \\ 1 & 4 \end{matrix} \right) \left( \begin{matrix} x \\ y \end{matrix} \right) = \left( \begin{matrix} 1 \\ 4 \end{matrix} \right) \pmod {11}$. The matrix has determinant $5$ which is invertible $\mod 11$, therefore the matrix itself is invertible and its inverse is $\left( \begin{matrix} 3 & 6 \\ 2 & 7 \end{matrix} \right)$, therefore $\left( \begin{matrix} x \\ y \end{matrix} \right) = \left( \begin{matrix} 3 & 6 \\ 2 & 7 \end{matrix} \right) \left( \begin{matrix} 1 \\ 4 \end{matrix} \right) \pmod {11} = \left( \begin{matrix} 5 \\ 8 \end{matrix} \right)$.

Alternatively, if you haven't studied matrices, multiply the second equation by $2$ in order to get $2x + 8y = 8 \pmod {11}$, then subtract the first equation from it and obtain $5y = 7 \pmod {11}$, and thus $y = 5^{-1} \cdot 7 = 9 \cdot 7 = 63 = 8 \pmod {11}$, and now use this to find $x$ from the second original equation $x = 4 - 4y = -28 = 5 \pmod {11}$.