#include <cstdio>

using namespace std;
int n,a,aux,xo,xi,x,r,c;
int main()
{
    freopen ("inversmodular.in", "r", stdin);
    freopen ("inversmodular.out", "w", stdout);

    scanf ( "%d%d", &a, &n );

    xo=1; xi=0;
    aux=n;

    while (aux!=0)
    {
        r=a%aux;
        c=a/aux;
        a=aux; aux=r;
        x=xo-c*xi;
        xo=xi;
        xi=x;
    }

    if(xo<0) xo+=n;
    printf("%d\n", xo);

    return 0;
}