How to solve a system of linear equations modulo n?

Solution 1:

First you can multiply the system by any number that has an inverse, that is $\gcd(x,20)=1$.

So in particular you cannot multiply or divide by $2,4,5,10$ as you would not multiply or divide by $0$ in a normal non-modular system. Well you can do it, but you'll loose equivalence in the way.

For instance here we would like to have $4x-3x$. We notice that $7^{-1}=3\pmod {20}$ so let's multiply the second line by $9$.

$\begin{cases} 4x-10y\equiv 8\pmod{20}\\ 7x+2y\equiv 5\pmod{20}\end{cases}\iff\begin{cases} 4x-10y\equiv 8\pmod{20}\\ 3x+18y\equiv 5\pmod{20}\end{cases}$

Now we can subtract two lines like we do in normal systems

$\begin{cases} 4x-10y\equiv 8\pmod{20}\\ x-28y\equiv 3\pmod{20}\end{cases}\iff\begin{cases} 4x-10y\equiv 8\pmod{20}\\ x\equiv 8y+3\pmod{20}\end{cases}$

We now have $x$ and can report in the first equation

$\begin{cases} 32y+12-10y\equiv 8\pmod{20}\\ x\equiv 8y+3\pmod{20}\end{cases}\iff\begin{cases} 2y\equiv 16\pmod{20}\\ x\equiv 8y+3\pmod{20}\end{cases}$

$2$ is not invertible modulo $20$ but since all coefficients are even, we can divide everything by $2$ including the modulo.

$\begin{cases} y\equiv 8\pmod{10}\\ x\equiv 8y+3\pmod{20}\end{cases}$

Finally report in second equation to get $x$, by introducing a dummy variable $k$ for expressing $y$

$\begin{cases} y\equiv 8\pmod{10}\\ x\equiv 8(10k+8)+3\pmod{20}\equiv 64+3\equiv 7 \pmod{20}\end{cases}$

I have detailed a lot, since this is apparently your first time solving this.

Answering question in comment

$\begin{cases} 2x-6y\equiv 11\pmod{20}\\ 4x+8y\equiv 9\pmod{20}\end{cases}$

Rem: for parity reasons this has no solution, but let's do like we ignore that.

For this one $9$ and $11$ are invertible (and their own inverse), so let's multiply the lines by $9$ and $11$.

You get

$\begin{cases} 2x+14y\equiv 1\pmod{20}\\ 16x+12y\equiv 1\pmod{20}\end{cases}\iff \begin{cases} 2x+14y\equiv 1\pmod{20}\\ 14x-2y\equiv 0\pmod{20}\end{cases}$

Which reduce to $y\equiv 7x\pmod{10}$, and this system has no solution ($2x+14y$ is divisible by $20$).

Solution 2:

\begin{eqnarray} 4x - 10y \equiv 8\pmod {20} \\ 7x + 2y \equiv 5\pmod {20} \end{eqnarray}

Method 1 - Take advantage of a unit coefficient (7)

\begin{align} 7x + 2y &\equiv 5\pmod {20} \\ 21x + 6y &\equiv 15\pmod {20} \\ x + 6y &\equiv 15\pmod {20} \\ x &\equiv 14y + 15 \pmod{20} \\ \hline 4(14y + 15) - 10y &\equiv 8\pmod {20} \\ 46y + 60 &\equiv 8 \pmod{20} \\ 6y &\equiv 8 \pmod{20} \\ 3y &\equiv 4 \pmod{10} \\ 21y &\equiv 28 \pmod{10} \\ y &\equiv 8 \pmod{10} \\ y &= 8 + 10 t \\ \hline x &\equiv 14(8 + 10 t) + 15 \pmod{20} \\ x &\equiv 112 + 140t + 15 \pmod{20} \\ x &\equiv 7 \pmod{20} \\ y &\equiv 8 \pmod{10} \\ \end{align}

Method 2 - Convert to prime-power moduli

\begin{eqnarray} 2y &\equiv 0\pmod 4 \\ 3x + 2y &\equiv 1\pmod 4 \\ \hline y &\equiv 0 \pmod 2 \\ \hline 3x &\equiv 1\pmod 4 \\ 9x &\equiv 3\pmod 4 \\ x &\equiv 3 \pmod 4 \end{eqnarray}

\begin{eqnarray} 4x &\equiv 3\pmod 5 \\ 2x + 2y &\equiv 0\pmod 5 \\ \hline -4x &\equiv -3 \pmod 5 \\ x &\equiv 2 \pmod 5 \\ \hline 4 + 2y &\equiv 0\pmod 5 \\ 2 + y &\equiv 0 \pmod 5 \\ y &\equiv 3 \pmod 5 \end{eqnarray}

$\left\{ \begin{array}{c} x \equiv 3 \pmod 4 \\ x \equiv 2 \pmod 5 \\ \end{array} \right\} \implies \left\{ \begin{array}{c} 5x \equiv 15 \pmod{20} \\ -4x \equiv -8 \pmod{20} \\ \end{array} \right\} \implies x \equiv 7 \pmod{20}$

$\left\{ \begin{array}{c} y \equiv 0 \pmod 2\\ y \equiv 3 \pmod 5 \\ \end{array} \right\} \implies \left\{ \begin{array}{c} -5y \equiv 0 \pmod{10} \\ 6y \equiv 18 \pmod{10} \\ \end{array} \right\} \implies y \equiv 8 \pmod{10}$