program wto;
var 
   a,b,x,y,c:int64;
function exgcd(a,b:int64;var x,y:int64):int64;
var tx,ty,t:int64;
begin
   if b=0 then 
     begin
        x:=1;
        y:=0;
        exit(a);
     end
   else 
     begin
        t:=exgcd(b,a mod b,tx,ty);
        x:=ty;
        y:=tx-(a div b)*ty;
        exit(t);
     end;
end;
begin
   assign(input,'mod.in');
   reset(input);
   assign(output,'mod.out');
   rewrite(output);
   read(a,b);
   c:=exgcd(a,b,x,y);
   while x<0 do x:=x+b;
   write(x);
   close(input);
   close(output);
end.