Answer to Question #261237 in Discrete Mathematics for King

Question

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

step by step solution

Answer 1

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.$