How to solve system of equations with mod?

Question

I'm trying to solve for $a$ and $b$: $$5 \equiv (4a + b)\bmod{26}\quad\text{and}\quad22\equiv (7a + b)\bmod{26}.$$ I tried looking it up online, and the thing that seemed most similar was the Chinese remainder theorem; however, I couldn't find an instance where it fit something more like what I want to solve. A simple explanation or a reference to one would be most appreciated.

With my (limited) knowledge of algebra, I figured out that $x\ \textrm{mod}\ 26 = x - 26\lfloor\frac{x}{26}\rfloor$, so I tried substituting that into my equations: $$5=(4a+b)-26\left\lfloor\frac{4a+b}{26}\right\rfloor\quad\text{and}\quad 22=(7a+b)-26\left\lfloor\frac{7a+b}{26}\right\rfloor.$$

And I figured I could do something with that since I got rid of the mod, but... I have never solved an equation with a floor function before.

Answer 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$.

Answer 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}$.

Answer 3

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