#include <fstream>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int a, l, lp,k, kp, n;
void cmmdc(int x, int y)
{
    if(y)
    {
        cmmdc(y, x%y);
        l=kp-lp*(x/y), k=lp;
        lp=l,kp=k;
    }
    else
        kp=k=1;
}
int main()
{
    fin>>a>>n;
    cmmdc(a, n);
    fout<<k;
    return 0;
}