Program inversmodular;
 var t,x,y,c,d,i,a,b:longint;
     fi,fo:text;
procedure euclid(a,b:longint; var d,x,y:longint);
 var xo,yo:longint;
begin
 if b=0 then begin d:=a; x:=1; y:=0; end
 else begin euclid(b,a mod b,d,xo,yo); x:=yo; y:=xo-(a div b)*yo; end;
end;
begin
 assign(fi,'inversmodular.in');
  assign(fo,'inversmodular.out');
 reset(fi); rewrite(fo);
    readln(fi,a,b); c:=1; d:=0;
      euclid(a,b,d,x,y);
    while x<0 do x:=x+b;
    writeln(fo,x);
 close(fo);
end.