program inversmodular;
var f,g:text;
    a,n,x,y,i,j,aux,cat,rest,m,u,v,n1,q,r,u1,v1:longint;
begin
        assign(f,'inversmodular.in'); reset(f);
        assign(g,'inversmodular.out'); rewrite(g);
        readln(f,a,n);
        n1:=n;
        x:=1; v:=1;
        while n <> 0 do
                begin
                q:= a div n; r:= a mod n;
                u1:=x-u*q; v1:=y-v*q;
                a:=n; n:=r; x:=u; y:=v; u:=u1; v:=v1;
                end;
        if x < 0 then x:=n1+ x mod n1;
        writeln(g,x);
        close(f); close(g);
end.