Этот алгоритм можно найти в интернете. Реализация пишется на языке C. Редко когда можно найти на паскале, ведь на нём писать этот алгоритм неудобно... Но я сделал....
Не могли бы вы мне помочь с оптимизацией??
Код

type mt=array[1..4] of integer;
var a:mt;
function euc(c:mt):mt;
var d:longint;
    k,k2:mt;
begin
if (c[2]>c[1]) then
begin
k[2]:=c[1];
k[1]:=c[2];
k[3]:=c[4];
k[4]:=c[3];
euc(k);
end;
if (c[2]=0) then
begin
euc[1]:=c[1];
euc[2]:=0;
euc[3]:=1;
euc[4]:=0;
end
else
begin
k2[1]:=c[2];
k2[2]:=c[1] mod c[2];
k2[3]:=0;
k2[4]:=0;
euc[1]:=euc(k2)[1];
euc[2]:=euc(k2)[2];
euc[3]:=euc(k2)[4];
euc[4]:=euc(k2)[3]-trunc(c[1] div c[2])*euc(k2)[4];
end;
end;

begin
read(a[1],a[2]);
a[3]:=0;
a[4]:=0;
a:=euc(a);
write(a[1],' ',a[3],' ',a[4]);
end.