# Solving $4$ simultaneous linear equations modulo $26$

I'm trying to solve these equations to solve a ciphertext which is encrypted by the Hill Cipher. I tried to solve these equations algebraically. (First choose two of them and try to eliminate one variable and after that choose another two and try the same thing for achieving two unknown two equations etc...)

\begin{align*} \tag{1}7a + 24b + 6c &= 1 \mod 26 \\ \tag{2}16a + 2b + 20c &= 0 \mod 26 \\ \tag{3}9a + 13b + 13c &= 10 \mod 26 \\ \tag{4}10a + 15b + 6c &= 17 \mod 26 \end{align*}

After this method I got $a = 17$, $b = 1$ and $c = 24$ and $a = 17$, $b = 1$, $c = 11$. However, it did not work with all of the four equations. Is there another way to solve these equations?

-
Try the Chinese Remainder Theorem; it should make stuff easier. – Lord_Farin Oct 22 '12 at 12:00
How can I apply Chinese Remainder Theorem in these equation? – Tugkan Oct 22 '12 at 12:02
To solve them modulo $2$ and modulo $13$, then reconstruct the solutions. It makes deriving $a = 17$ very easy (first and third equations). – Lord_Farin Oct 22 '12 at 12:03
The "algebraic way" should work, provided you remember to do all your arithmetic modulo 26, and remember not to divide or multiply by anything that isn't prime to 26. – Gerry Myerson Oct 22 '12 at 12:07
Multiplying should be harmless, though... – Lord_Farin Oct 22 '12 at 12:09

As suggested by Lord_Farin, consider the equations modulo $2$ and modulo $13$ separately. Modulo $2$ you get

\begin{align} a &\equiv 1 \mod 2 \\ 0 &\equiv 0 \mod 2 \\ a + b + c &\equiv 0 \mod 2 \\ b &\equiv 1 \mod 2 \end{align}

which has solutions $\boxed{(a,b,c) \equiv (1,1,0) \mod 2}$. Modulo $13$ is a bit harder, but we get

\begin{align} -6a - 2b + 6c &\equiv 1 \mod 13 \\ 3a + 2b - 6c &\equiv 0 \mod 13 \\ -4a &\equiv -3 \mod 13 \\ -3a + 2b + 6c &\equiv 4 \mod 13 \end{align}

Using the third equation first, we get $a \equiv 4 \mod 13$, so that the other three become

\begin{align} -2b + 6c &\equiv -1 \mod 13 \\ 2b - 6c &\equiv 1 \mod 13 \\ 2b + 6c &\equiv 3 \mod 13 \end{align}

Solving for $b$ and $c$, we get $b \equiv 1 \mod 13$ and $c \equiv 11 \mod 13$. So modulo $13$, the numbers $a,b,c$ satisfy $\boxed{(a,b,c) \equiv (4,1,11) \mod 13}$.

Combining the two boxes, we get the unique solution $\boxed{(a,b,c) \equiv (17,1,24) \mod 26}$.

-

Hint $\$ By $\rm (1)+(2),\,\ -3a \equiv 1\equiv 27,\:$ so $\rm\:a\equiv -9.\$ By $\rm (2)+(4),\,\ 17b\equiv 17,\:$ so $\rm\:b\equiv 1.$ Substituting in $\rm\:(3)\:$ yields $\rm\:6c\equiv -12\:$ so $\rm\:c\equiv -2\pmod{\color{#C00}{13}}.\:$ By $\rm\:(3)\,\ mod\ 2\!:\ c \equiv -a -b = 9-1\equiv 0,\:$ hence $\rm\:c\equiv -2\pmod{\color{#C00}{26}}.\:$ Indeed $\rm\:(a,b,c)\equiv (-9,1,-2)\:$ satisfies all equations.

-