Answer to Question #264361 in Discrete Mathematics for Helen

Question

Find the inverse of 35 modulo 11 by using extended Euclidean Algorithm

Answer 1

Let us find the inverse of 35 modulo 11 by using extended Euclidean Algorithm.

Taking into account that

$35=11\cdot 3+2\\$ and $11=2\cdot5+1,$

we conclude that

$1=11-2\cdot 5=11-(35-11\cdot 3)5=11\cdot 16+35(-5).$

It follows that

$11\cdot 16+35(-5)=1\ mod\ 11,$

and hence

$35(-5)=1\ mod\ 11.$

Since $-5\ mod\ 11=6\ mod\ 11,$ we conclude that the inverse of 35 modulo 11 is 6.