1
$\begingroup$

Find the multiplicative inverse of 11 in $\Bbb{Z}_{26}$

I used Extended Euclidean Algorithm to solve this problem. By Euclidean Algorithm,

$$ 26=11\times2+4\\ 11=4\times2+3\\ 4=3\times1+1\\ 3=1\times3+0 $$

GCD(26,11) is 1, so I can use Excluded Euclidean Algorithm and the result of equation have to be like $26\times s+11\times t=1$.

$$ 1=4-3\times1\\ 1=(26-11\times2)-(11-4\times2)\times1\\ 1=(26-11\times2)-(11-(26-11\times2)\times2)\\ 1=(26-11\times2)-(11-26\times2+11\times4)\\ 1=26-11\times2 -11+26\times2-11\times4\\ 1=26\times3-11\times7 $$

It means $1\equiv -11\times7 \ (\text{mod 11})$, but solution says 19 can be also answer. How to find 19 in this problem?

$\endgroup$
  • 3
    $\begingroup$ $-7\equiv 19\pmod {26}$. Just add $26$ to $-7$ to get $19$. $\endgroup$ – Mike Earnest Sep 13 '18 at 1:41
  • 1
    $\begingroup$ It means that $1\equiv -7\times 11$ is equal to $1\equiv 19\times 11$? $\endgroup$ – baeharam Sep 13 '18 at 1:43
  • 2
    $\begingroup$ Exactly! If $a\equiv b$, then $a\times c\equiv b\times c$. $\endgroup$ – Mike Earnest Sep 13 '18 at 1:44
  • $\begingroup$ I understood everything, but can you explain how just adding $26$ occurs other solution? Sorry for my stupid question. $\endgroup$ – baeharam Sep 13 '18 at 1:49
  • 1
    $\begingroup$ $26\equiv 0\pmod{26}$, so adding $-7$ to both sides, $19\equiv -7\pmod {26}$, so multiplying both sides by $11$, $19\times 11\equiv -7\times 11\equiv 1\pmod {26}$, proving $19$ is also an inverse. Does this help? $\endgroup$ – Mike Earnest Sep 13 '18 at 16:05

Your Answer

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

Browse other questions tagged or ask your own question.