program invers;
var f,g:text;
    a,n,x,y:int64;
procedure invers(var x,y:int64;a,b:int64);
var aux:int64;
  begin
    if b=0 then
           begin
             x:=1;
             y:=0;
           end
           else
           begin
             invers(x,y,b,a mod b);
             aux:=x;
             x:=y;
             y:=aux -a div b*y;
           end;
  end;
begin
  assign(f,'inversmodular.in');
  assign(g,'inversmodular.out');
  reset(f);
  rewrite(g);
  readln(f,a,n);
  invers(x,y,a,n);
  if x<=0 then
          repeat
            x:=x mod n +n;
          until x>0;
  writeln(g,x);
  close(f);
  close(g);
end.