Peter_APIIT

March 31st, 2009, 09:42 AM

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 ?

Please show example.

2. How to simplify the equation(*) ?

3. How human hand calculation differ to code implementation ?

Thanks for your help.

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 ?

Please show example.

2. How to simplify the equation(*) ?

3. How human hand calculation differ to code implementation ?

Thanks for your help.