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.
77=5(15)+25=2(2)+12=2(1)+02=77−5(15)1=5−2(2) Use the equations in the right side and perform reverse operation as:
1=5−2(2) 1=5−[77−5(15)](2)1=5(31)+77(−2) Therefore 1=77(−2)mod5, or of we prefer a residue value for multiplicative inverse
1=77(3)mod5. Therefore, 3 is the multiplicative inverse of 77.
Comments