CODEWITHSUNDEEP
algorithmmodulo
venkysmarty
venkysmarty

Reputation: 11431

modular inversion in algorithms

I am reading Extended Euclid algorithm in Algorithms book by Sanjoy das gupta at followinglink page 33

http://www.cse.iitd.ernet.in/~naveen/courses/CSL630/all.pdf

suppose we wish to compute 11^-1 mod 25. Using the extended Euclid algorithm, we find that 15 * 25 - 34 * 11 = 1. Reducing both sides modulo 25, we have -34 * 11 congruent equal 1 mod 25. So -34 congruent equal 16 mod 25 is the inverse of 11 mod 25.

My question how author concluded that "-34 congruent equal 16 mod 25 is the inverse of 11 mod 25." from previous statement.

Upvotes: 1

Views: 59

Answers (1)

clemens
clemens

Reputation: 17721

Since 15 * 25 - 34 * 11 = 1 you have 15 * 25 - 34 * 11 = 1 mod 25 which leads to -34 * 11 = 1 mod 25.

If you have a * b = 1, than a is the multiplicative inverse of b regardeless if a and b are matrices, field elements or elements of a residual class ring.

You get the result 16 when you normalize -34 to the range between 0 and 24: 16 = 2 * 25 - 34, and thus 16 * 11 = 1 mod 25. Note: There is exactly one natural k with k * 25 - 34 between 0 and 24, and this is 2 in this case.

Upvotes: 1

Related Questions