Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Extended Euclidean Algorithm Explanation Help and Modular Multiplicative Inverse (http://www.go4expert.com/forums/extended-euclidean-algorithm-t16704/)

 Peter_APIIT 29Mar2009 09:17

Extended Euclidean Algorithm Explanation Help and Modular Multiplicative Inverse

Hello to all, i have a hard time understand this these two topics.

I hope someone can clear my myth.

I do check the EEA page and did quite amount of research regarding this topic.

This is what i understand.

51x + 36y = gcd(a, b)
Rewrite them in quotient remainder theorem

Euclid Algorithm
51 = 1 x 36 + 15 52 / 36 = 3 r 6
36 = 2 x 15 + 6 36 / 15 = 2 r 6
15 = 2 x 6 + 3 15 / 6 = 2 r 3
6 = 2 x 3 + 0 6 / 2 = 3 r 0

Extended Euclidean Algorithm
=Take the last second solution

15 = 2 x 6 + 3
Rewrite the remainder at LHS

3 = 15 - 2 x 6
= 15 - 2 x (36 - 2 * 15)
= 5 * 15 - 2 * 36 (simplifying)(*)
= 5 * (51 - 36) - 2 * 36
= 5 * 51 - 7 * 36 (simplifying)(*)

Question
1. How modular multiplicative inverse related to EEA ?