Question

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

step by step solution

Answer 1

$35=3\times11+2...(1)\\ 11=5\times2+1...(2)\\ 2=2\times1+0\\$

Now,

$1=11-5\times2\ \text{From (2)}\\ 1= 11-5\times (35-3\times11) \ \text{From (1)}\\ 1= 11-5\times35+15\times11\\ 1=-5\times35+16\times11\\ 1(\text{mod 11})=6\times35+16\times11\\ 1(\text{mod 11})=6\times35$

$6\equiv 35^{-1} \text{mod 11}$