#include <fstream>

#define LL long long int

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

LL a, n;
LL x, y, d;

void euclidExtins(LL, LL, LL&, LL&, LL&);

int main()
{
    fin >>a>>n;
    euclidExtins(a, n, x, y, d);
    if (x < 0) x = x + ((-x) / n * n);
    fout <<x<<'\n';
    fout.close();
    return 0;
}

void euclidExtins(LL a, LL b, LL& x, LL& y, LL& d)
{
    if (b == 0)
    {
        d = a; x = 1; y = 0;
        return;
    }

    LL x0, y0;
    euclidExtins(b, a%b, x0, y0, d);
    x = y0; y = x0 - (a / b) * y0;
}