Program invmod;
var A,N, d,x,y : longint;
    fin,fout : text;


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



begin
assign(fin,'inversmodular.in');
reset(fin);
readln(fin,A,N);
close(fin);

cmmdc(A,N,d,x,y);
if x<0 then
while x<0 do
x:=x+N;
assign(fout,'inversmodular.out');
rewrite(fout);
writeln(fout,x);
close(fout);
end.