Understanding implementation of Extended Euclidean algorithm

Question

After some experimentation and search, I came up with the following definition:

emcd' :: Integer -> Integer -> (Integer,Integer,Integer)
emcd' a 0 = (a, 1, 0)
emcd' a b = 
  let (g, t, s) = emcd' b r
  in (g, s, t - (q * s))
    where
      (q, r) = divMod a b

What's the meaning behind this expression t - (q * s) ?

I've tried to evaluate it by hand; even though I arrived at the correct result (1, -4, 15), I can't see why that expression returns the value of t.

There is a famous method for calculating s and t in as + bt = gcd(a, b). In the process of finding the gcd, I get several equations.

By reversing the steps in the Euclidean Algorithm, it is possible to find these integers a and b. Those resulting equations look like the expression t - (q * s); however, I can't figure out the exact process.

Daniel Wagner · Accepted Answer · 2021-12-13 17:53:53Z

3

Since (q, r) = divMod a b, we have the equation

a = qb + r

and because of the recursive call, we have:

tb + sr = g

Substituting a-qb for r in the second equation, that means

tb + s(a-qb) = g
tb + sa - qsb = g
sa + (t-qs)b = g

This explains why s and t - q*s are good choices to return.

answered Dec 13, 2021 at 17:53

Daniel Wagner

156k10 gold badges231 silver badges392 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

F. Zer Over a year ago

Thank you so much for your answer. Could you explain this line, please ? "and because of the recursive call, we have: tb + sr = g"

Daniel Wagner Over a year ago

@F.Zer That's exactly the property you stated in the question... "Calculating s and t in as + bt = gcd(a, b)"

Collectives™ on Stack Overflow

Understanding implementation of Extended Euclidean algorithm

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related