Answer to Question #261235 in Combinatorics | Number Theory for King

Question

Find the inverse of 77 modulo 5 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(77, 5)=1.$

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

$$\def\arraystretch{1.5} \begin{array}{c:c} 77=5(15)+2 & 2=77-5(15) \\ 5=2(2)+1 & 1=5-2(2) \\ 2=2(1)+0 & \end{array}$$

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

$$\begin{matrix} 1=5-2(2)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ \\ \ \ \ 1=5-[77-5(15)](2)\\ \\ 1=5(31)+77(-2)\ \ \ \end{matrix}$$

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

$$1=77(3)\mod {5}.$$

Therefore, $3$ is the multiplicative inverse of $77.$