Extended Euclid Algo for finding the GCD of two integers. Works using Euclid's law: if `d` is the GCD of `a` and `b`, then there exists an `x` and `y` such that ```ax + by = d```

extended_euclid.m

%{
    Problem 7 (ii) - Extended Euclid

    Input:  positive integers a,b with a >= b >= 0
    Output: integer array [ x,y,d ] such that 
            d = gcd(a,b) and ax + by = d
%}
function result = extended_Euclid (a, b)

    if (b == 0)
        result = [ 1, 0, a ];
        return;
    end
        
    %M is a matrix of the form [x, y, d ]
    M = extended_Euclid(b, mod(a,b));
    
    % result is [ y, x - floor(a/b) * y, d ]
    result = [ M(2), M(1) - floor(a/b) * M(2), M(3) ];
    return
end