program inversmodular;
var     f,g:text;
        n,cat,rest,aux,u1,u,v,a,v1,x,y,i,j:longint;
begin
  assign(f,'inversmodular.in'); reset(f);
  assign(g,'inversmodular.out'); rewrite(g);
  readln(f,a,n);
  aux:=n; x:=1; y:=0; u:=0; v:=1;
  while n<>0 do
    begin
      cat:=a div n; rest:=a mod n;
      u1:=x-u*cat; v1:=y-v*cat;
      a:=n;
      n:=rest;
      x:=u;
      y:=v;
      u:=u1;
      v:=v1;
    end;
  if x<0 then x:=aux+x mod aux;
  writeln(g,x);
  close(f); close(g);
end.