program pascal;
var f,g:text; a,n,x,y,b:int64;

 procedure cmmdc(x,y:int64);
 var aux:int64;
 begin
 if y=0 then begin a:=1; b:=0; end
        else begin
             cmmdc(y,x mod y);
             aux:=a;
             a:=b;
             b:=aux-b*(x div y);
             end;
 end;

begin
assign(f,'inversmodular.in'); reset(f);
assign(g,'inversmodular.out'); rewrite(g);
read(f,x,y);
cmmdc(x,y);
if a<=0 then a:=y+a mod y;
write(g,a);
close(f);
close(g);
end.