9
$\begingroup$

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.

Improve this question
$\endgroup$
10
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ Awesome. I only have one last question to clarify. To obtain b, do I need to repeat the whole process, but this time substituting it the other way around or... Is there a faster way? I tried plugging the value of a in the second equation, but in the end I got a fraction... Unless I did it incorrectly, because just seeing mod there messes me up. $\endgroup$ – Emyr Sep 27 '12 at 23:13
  • $\begingroup$ Yes, a fraction, can be. But fractions are not meant like rational numbers in the $\bmod$ systems. What is the denominator? If it is $z$, find its 'reciprocial' $y$ which satisfies $yz\equiv 1$. $\endgroup$ – Berci Sep 30 '12 at 23:29
  • 1
    $\begingroup$ in python How I will be able to solve that equation? $\endgroup$ – juaninf Oct 23 '13 at 12:42
9
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ Thank you, so much! I admit I'm still having trouble with it, though. From reading about the Euclidean Algorithms, am I right to assume that 15 is the greatest common divisor of 7 and 3? My only question regarding that aspect is how does it turn from 3 = 7 a (mod 26) to 19 = a (mod 26) by multiplying it by 15? I feel like it sounds like a pretty obvious question, but I can't figure it out... Also, if you would be so kind to provide me a fairly simple reading on the euclidean algorithm to be able to do what you did there, I would be quite grateful! (Wiki is hard ): ) $\endgroup$ – Emyr Sep 28 '12 at 0:43
  • $\begingroup$ @Emyr: The Euclid-Wallis Algorithm keeps track of what is computed in the Euclidean Algorithm. Use it to solve $7x+26y=1$ to get that $7\times15=1\pmod{26}$. $\endgroup$ – robjohn♦ Sep 28 '12 at 4:46
1
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

Well, in this answer I will use matrices to solve the problem. For that, I will transform the given equations to a matrix equation.

$$5 \equiv 4a+b \,(mod \,26)$$ $$22 \equiv 7a+b \,(mod \,26)$$ $$ \implies \begin{bmatrix} 5 \\ 22 \end{bmatrix} = \begin{bmatrix}4 & 1 \\ 7 & 1 \end{bmatrix} \begin{bmatrix}a \\ b \end{bmatrix} (\text{mod 26}) $$

and the values of a,b can be obtained using the following,

$$ \begin{bmatrix} a \\ b \end{bmatrix}=A^{-1}\begin{bmatrix} 5 \\ 22 \end{bmatrix} \, (mod \, 26) $$ Where, $$ A=\begin{bmatrix}4 & 1 \\ 7 & 1 \end{bmatrix} \, (mod \,26) $$ $$ \therefore det(A) = (4\times1-7\times1)\,(mod\,26) = -3\,(mod\,26)=23 $$

Also, $23^{-1}=23^{12-1}\,(mod\,26)=17\,(mod\,26)$ $$ \therefore A^{-1}=17\times\begin{bmatrix} 1&-1 \\ -7&4 \end{bmatrix} \, (mod \,26) $$

$$ \implies A^{-1}=\begin{bmatrix} 17&9 \\ 11&16 \end{bmatrix} \,(mod \,26) $$

$$ \therefore \begin{bmatrix} a \\ b \end{bmatrix}=\begin{bmatrix} 17&9 \\ 11&16 \end{bmatrix} \begin{bmatrix} 5 \\ 22 \end{bmatrix} \,(mod \,26) $$

By multiplying the above two matrices and taking the $mod \,26$ you will get, $$a=23,\, b=17$$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.