Question #261235

Find the inverse of 77 modulo 5 by using extended Euclidean Algorithm



Step by step solution


1
Expert's answer
2021-11-05T10:32:35-0400

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

It will verify that GCD(77,5)=1.GCD(77, 5)=1.

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


77=5(15)+22=775(15)5=2(2)+11=52(2)2=2(1)+0\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:


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

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


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

Therefore, 33 is the multiplicative inverse of 77.77.



Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!
LATEST TUTORIALS
APPROVED BY CLIENTS