var

a,b,x,y,k:longint;

function gcd(a,b:longint;var x,y:longint):longint;

var t:longint;

begin

if b=0 then

begin

x:=1;y:=0;exit(a);

end;

gcd:=gcd(b,a mod b,x,y);

t:=x;

x:=y;

y:=t-(a div b)*y;

end;

begin

readln(a,b);

k:=gcd(a,b,x,y);

writeln((x+b) mod b);

end.

大家可以去看看欧几里德算法的扩展

附上欧几里德算法最大公约数的求法

function gcd(a,b:integer):integer;

if b=0 then gcd:=a;

else gcd:=gcd(b,a mod b);

end.