# How to solve congruence modulo equations?

While studying Affine Cipher in cryptography it tells that we need to solve a system of modulo congruence equations.

The equations are:

1. $8\alpha+\beta\equiv 15 \pmod{26}$
2. $5\alpha+\beta\equiv 16 \pmod{26}$

Could anyone tell how to solve these equations.

• $\beta\equiv 15-8\alpha\,\Rightarrow\, 5\alpha + (15-8\alpha)\equiv 15-3\alpha\equiv 16\iff 3\alpha\equiv -1\equiv -27$ $\stackrel{:3}\iff \alpha\equiv -9\equiv 17$ mod $26$. So $8(17)+\beta\equiv 15\iff \beta\equiv 9$ mod $26$. – user26486 May 13 '15 at 14:44
• @user31415:That's a good answer.Could you tell me how $-1 \equiv -27$ came?Also why always we place equivalence symbol in these equations when an equal symbol is enough to get $\alpha$ and $\beta$? – justin May 14 '15 at 9:24
• $-1 = -27 + 26(1)$, so $-1$ and $-27$ give same remainders when divided by $26$. Definition: $a\equiv b\pmod{\! n}\!\iff\! n\mid a-b$ or i.e. $a,b$ leave same remainders when divided by $n$. It is nitpicking about notation whether you can write equality symbols in place of equivalences there, but I would just write equivalences everywhere. I could later divide both sides by $3$ because $(26,3)=1$. It is because $26\mid 3(\alpha-(-9))\!\iff\! 26\mid \alpha-(-9)$, which may make this division property more apparent. Remember Fundamental theorem of arithmetic. – user26486 May 14 '15 at 10:19
• @user31415:Okay that's right.Yeah I'll go with equivalence.Is it sure that for any numbers m and n if (m,n)=1 you could divide both sides of the equivalence by n?How did you get -27 in the R.H.S?Is it a guess or is there any strategy to follow for finding -27?Also couldn't get how you wrote $26\mid 3(\alpha-(-9))$ while I think we just need to consider $26\mid 3\alpha$? – justin May 14 '15 at 12:21
• @user31415:Yeah got it.Could you tell how did you changed $26\mid \alpha-(-9)$ into $\alpha\equiv-9 \equiv 17$ mod 26?Does this use the same logic you stated in previous comment?Also how to find the value of $\alpha$ from $\alpha\equiv-9 \equiv 17$ mod 26?Is it($\alpha$) -9 or 17? – justin May 14 '15 at 12:37

On subtraction, $$3\alpha\equiv-1\pmod{26}\equiv-1+2\cdot26$$

As $(3,26)=1,$ $$\alpha\equiv17\pmod{26}$$

and $$\beta\equiv15-8\alpha\pmod{26}\equiv?$$

• :Could you tell how did you get (-1+2.26) on the R.H.S in the first line of the answer? – justin May 11 '15 at 9:48
• @justin, As $52\equiv0\pmod{26},51\equiv-1$ – lab bhattacharjee May 11 '15 at 10:14
• :Could you tell how did you get 52?Do you mean to say that when we subtract these equations we would get $52 \equiv 0 \pmod{26}$? – justin May 11 '15 at 10:23
• @justin, We need to find a value of $y$ such that $3|(26y-1)$ . By observation, $y=2$ is one of such values – lab bhattacharjee May 11 '15 at 10:24
• :Could you tell why do we need to get a value of y for $3|(26y-1)$ when the equation is just $3\alpha\equiv-1\pmod{26}$ where there is no y? – justin May 11 '15 at 10:44