[Haskell-beginners] extended gcd

[Daniel Fischer]

On Dienstag, 11. Dezember 2012, 14:53:28, Zbigniew Stanasiuk wrote:
> Hallo everyone,
> 
> I try to understand how the following recursive function works:
> 
> extGCD :: Integer -> Integer -> [Integer]
> extGCD a 0 = [1, 0, a]
> extGCD a b = let (q, r) = a `quotRem` b
>                         [s, t, g] = extGCD b r
>                      in  [t, s - q * t, abs g]
> 
>  Some hints to explain??

It should return a triple rather than a list.

That said, the function should have the property

extGCD a b = [s, t, g]

    <=>

g = gcd a b and s*a + t*b = g

++++

Now, we prove that property by induction on the absolute value of b.

It is easily checked in the case that b = 0.

extGCD a 0 = [1, 0, a];

gcd a 0 = a, and 1*a + 0*0 = a

Suppose it holds for all (x, y) with |y| < |b|.

Then if

(q,r) = a `quotRem` b

we have |r| < |b|, hence for

[s, t, g] = extGCD b r we have

1. g = gcd b r
2. s*b + t*r = g

by the induction hypothesis.

Now,

gcd a b = gcd (q*b + r) b = gcd r b = gcd b r = g

and

g = s*b + t*r = s*b + t*(a - q*b) = t*a + (s - q*t)* b

c.q.f.d.