Program Inversmodular;
var a,n,x : longint;

procedure Citeste;
var Intrare : text;
begin
  assign(Intrare,'inversmodular.in');
  reset(Intrare);
  readln(Intrare,a,n);
  close(Intrare);
end;

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

procedure Calculeaza;
var y : longint;
begin
  euclid(a,n,x,y);
  while x<1 do x:=x+n;
end;

procedure Scrie;
var Iesire : text;
begin
  assign(Iesire,'inversmodular.out');
  rewrite(Iesire);
  write(Iesire,x);
  close(Iesire);
end;

begin
  Citeste;
  Calculeaza;
  Scrie;
end.