Use the extended Euclidean algorithm by hand to find the inv

Use the extended Euclidean algorithm, by hand, to find the inverse of 46 modulo 67.

Solution

67=46+21              , 21=67-46

46=21*2+4             , 4=46-21*2=46*3-2*67

21=4*5+1              ,1=21-4*5=67-46-5*(46*3-2*67)=11*67-16*46

So,

1=11*67-16*46

Hence, 1=-16*46 mod 67

So, -16=67-16=51 is the inverse of 46 modulo 67