program inversmodular;
  var a,n,d:longint;
      x,y,z:longint;

function gcd(a,b:longint):longint;

  begin
    if b=0 then
      begin
        gcd:=a;
        x:=1;y:=0;
      end else
      begin
        gcd:=gcd(b,a mod b);
        z:=x;
        x:=y;
        y:=z-(a div b)*x;
      end;
  end;

begin
  assign(input,'inversmodular.in');
  reset(input);
  assign(output,'inversmodular.out');
  rewrite(output);

  readln(a,n);
  d:=gcd(n,a);
  if y<0 then y:=y+((-y)div n+1)*n;
  y:=y mod n;
  writeln(y);
  close(output);
end.