How to solve system of equations with mod?

Solution 1:

Well, mod is easier to handle. We have only $m$ numbers $\pmod m$: $0,1,\dots,m-1$ and already $m\equiv 0$ (also, $-1\equiv m-1$), it goes in a cycle just like the hours in a day $\pmod{12}$.

Precisely, $a\equiv b \pmod m$ means $\ m|(a-b)$, and the arithmetic operations such as $+,-,\cdot$ are very friendly with it, $\equiv$ acts just like an equation.

You can try to solve it, like $b\equiv 22-7a \pmod{26}$, then substitute it back to the other, $5\equiv -3a+22 $, so $3a\equiv 17$, but $\pmod{26}$ this $17$ can be substituted by $-9$ for example (because $17\equiv -9 \pmod{26}$), and $3$ is coprime to $26$ so one can divide by $3$.

Solution 2:

Since everything is $\bmod{26}$, you can use most of the methods for solving other simultaneous equations. Instead of dividing to get fractions, use modular division (which involves the Euclideam Algorithm).

For example, let's use Gaussian elimination for this problem $$ \begin{align} 12&=2a+b\pmod{26}\\ 15&=9a+b\pmod{26} \end{align} $$ Subtracting the first from the second gives $$ 3=7a\pmod{26} $$ Using the Euclidean Algorithm, we get that $15\times7=105\equiv1\pmod{26}$. So, multiplying both sides by $15$ we get $$ 19=a\pmod{26} $$ Subtracting $2$ times the second from $9$ times the first yields $$ 78=7b\pmod{26} $$ Since $78\equiv0\pmod{26}$, multiplying both sides by $15$ yields $$ 0=b\pmod{26} $$

Using the Euclid-Wallis Algorithm

As described in this answer, we can use the Euclid-Wallis Algorithm to invert $7\bmod{26}$: $$ \begin{array}{rrrrrrr} &&\color{orange}{3}&\color{orange}{1}&\color{orange}{2}&\color{orange}{2}\\ \hline \color{#00A000}{1}&\color{#00A000}{0}& 1&-1&\color{red}{3}&\color{blue}{-7}\\ \color{#00A000}{0}& \color{#00A000}{1}& -3&4&\color{red}{-11}&\color{blue}{26}\\ \color{#00A000}{26}&\color{#00A000}{7}&5& 2& \color{red}{1}&\color{blue}{0} \end{array} $$ This says that $3\times26-11\times7=1$, which says that $-11\times7\equiv1\pmod{26}$. Since $-11\equiv15\pmod{26}$, we also get $15\times7\equiv1\pmod{26}$.

Solution 3:

Hint: $b \equiv 5 - 4 a \mod 26$; plug this in to your second equation.