# include <fstream>
# include <algorithm>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int i,j,n,a;
long long euclid (int a, int b, long long &x, long long &y)
{
    if (b==0)
    {
        x=1; y=0;
        return a;
    }
    long long D, x0, y0;
    D=euclid (b, a%b, x0, y0);
    x=y0;
    y=x0 - (a/b)*y0;
    return D;
}
int main ()
{
    f>>a>>n;

    long long D, x, y;
    D=euclid (a, n, x, y);

    if (x<0) x=n+x%n;

    g<<x<<"\n";

    return 0;
}