Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
show 4 more comments

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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