#include <fstream>

#define LL long long int

using namespace std;

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

LL t;
LL a, b, c;
LL d, x, y;
LL i, j;

void euclid(LL, LL, LL&, LL&, LL&);

int main()
{
    fin >>a>>b;
    euclid(a, b, d, x, y);
    while (x < 0) x += b;
    fout <<x<<'\n';
    fout.close();
    return 0;
}

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

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