#include <bits/stdc++.h>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

void euclid(long long int a, long long int b, long long int  &d, long long int &x, long long int &y)
{   if(b==0)
    {   x=1;
        y=0;
        d=a;
    }
    else
    {   long long int x0, y0;
        euclid(b, a%b, d, x0, y0);
        x=y0;
        y=x0-(a/b)*y0;
    }
}

int main()
{   long long int A, X, Y, N, d;
    f>>A>>N;
    euclid(A, N, d, X, Y);
    if(1%d!=0)
    {   X=0;
        Y=0;
    }
    else
    {   X=X*1/d;
        Y=Y*1/d;
    }
    if(X<0&&X>-N+1)
        X=X+N;
    g<<X;
    return 0;
}