# Confused about multiplicative inverse of 11 in $\Bbb{Z}_{26}$?

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?

• $-7\equiv 19\pmod {26}$. Just add $26$ to $-7$ to get $19$. – Mike Earnest Sep 13 '18 at 1:41
• It means that $1\equiv -7\times 11$ is equal to $1\equiv 19\times 11$? – baeharam Sep 13 '18 at 1:43
• Exactly! If $a\equiv b$, then $a\times c\equiv b\times c$. – Mike Earnest Sep 13 '18 at 1:44
• I understood everything, but can you explain how just adding $26$ occurs other solution? Sorry for my stupid question. – baeharam Sep 13 '18 at 1:49
• $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? – Mike Earnest Sep 13 '18 at 16:05