0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $\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$. $\endgroup$ – user26486 May 13 '15 at 14:44
  • $\begingroup$ @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$? $\endgroup$ – justin May 14 '15 at 9:24
  • $\begingroup$ $-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. $\endgroup$ – user26486 May 14 '15 at 10:19
  • $\begingroup$ @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$? $\endgroup$ – justin May 14 '15 at 12:21
  • $\begingroup$ @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? $\endgroup$ – justin May 14 '15 at 12:37
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ :Could you tell how did you get (-1+2.26) on the R.H.S in the first line of the answer? $\endgroup$ – justin May 11 '15 at 9:48
  • $\begingroup$ @justin, As $52\equiv0\pmod{26},51\equiv-1$ $\endgroup$ – lab bhattacharjee May 11 '15 at 10:14
  • $\begingroup$ :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}$? $\endgroup$ – justin May 11 '15 at 10:23
  • $\begingroup$ @justin, We need to find a value of $y$ such that $3|(26y-1)$ . By observation, $y=2$ is one of such values $\endgroup$ – lab bhattacharjee May 11 '15 at 10:24
  • $\begingroup$ :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? $\endgroup$ – justin May 11 '15 at 10:44

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.