var s,d,x,y,a,b,n:int64;
procedure euclid_extins(var x,y:int64; a,b:int64);
   var aux:int64;
   begin
     if b=0 then
       begin
         x:=1; y:=0;
       end
             else
       begin
         euclid_extins(x,y,b,a mod b);
         aux:=x;
         x:=y;
         y:=aux-y*(a div b);
       end;
   end;
begin
assign(input,'inversmodular.in'); reset(input);
assign(output,'inversmodular.out'); rewrite(output);
readln(a,n);
s:=0;
euclid_extins(s,d,a,n);
while s<=0 do s:=n+s mod n;
writeln(s);
close(input);
close(output);
end.