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

1=11*67-16*46

-16*46=1 mod 67

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