var a,n,d,x,y:longint;

procedure gcd(a,n:longint; var d,x,y:longint);
  var x0,y0:longint;
  begin
    if n=0 then begin
      d:=a;
      x:=1;
      y:=0;
    end else begin
      gcd(n,a mod n,d,x0,y0);
      x:=y0;
      y:=x0-(a div n)*y0;
    end;
  end;

begin
  assign(input,'inversmodular.in');
  reset(input);
  assign(output,'inversmodular.out');
  rewrite(output);
  readln(a,n);
  gcd(a,n,d,x,y);
  if x<0 then x:=n+x mod n;
  write(x);
  close(input);
  close(output);
end.