function [d,u,v] = euclidesExt(a,b)
% EUCLIDESEXT Implements the Extended Euclidean Algorithm.
%
% [D,U,V] = EUCLIDESEXT(A,B) where D is the greatest common divisor of A
% and B, being U and V rational numbers.
% Copyright (C) Iván López Espejo 2011
% Version: Id: euclidesExt.m , v 1.0 2011
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% This program is free software; you can redistribute it and/or modify
% it under the terms of the GNU General Public License as published by
% the Free Software Foundation; either version 2 of the License, or
% (at your option) any later version.
%
% This program is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
% GNU General Public License for more details.
%
% You can obtain a copy of the GNU General Public License from
% ftp://prep.ai.mit.edu/pub/gnu/COPYING-2.0 or by writing to
% Free Software Foundation, Inc.,675 Mass Ave, Cambridge, MA 02139, USA.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
u2 = 1;
v2 = 0;
u1 = 0;
v1 = 1;
r1 = -1;
while true
c = floor(a/b);
r = mod(a,b);
u = u2 - c*u1;
v = v2 - c*v1;
if r == 0
d = r1;
u = u1;
v = v1;
break;
else
r1 = r;
a = b;
b = r1;
u2 = u1;
v2 = v1;
u1 = u;
v1 = v;
end
end