Find the inverse of 55 modulo 7 by using extended Euclidean Algorithm step by step solution

Apply Euclidean Algorithm to compute GCD as shown in the left column.

It will verify that $GCD(55, 7)=1.$

Then we will solve for the remainders in the right column.

$\def\arraystretch{1.5} \begin{array}{c:c} 55=7(7)+6 & 6=55-7(7) \\ 7=6(1)+1 & 1=7-6(1) \\ 6=1(6)+0 & \end{array}$

Use the equations in the right side and perform reverse operation as:

$\begin{matrix} 1=7-6(1)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ \\ \ \ \ 1=7-[55-7(7)](1)\\ \\ 1=7(8)+55(-1)\ \ \ \end{matrix}$

Therefore $1=55(-1)\mod {7},$ or of we prefer a residue value for multiplicative inverse

$1=55(6)\mod {7}.$

Therefore, $7$ is the multiplicative inverse of $55.$