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

83 Views Asked by At

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?