#include <fstream>
using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");
long long x,y,x0,y0,a,n;
void euclid_extins (long long a,long long b)
{
    if (b==0)
    {
        x=x0=1;
        y=y0=0;
    }
    else
    {
        euclid_extins (b,a%b);
        x=y0;
        y=x0-(a/b)*y0;
        x0=x;
        y0=y;
    }
}
int main ()
{
    fin>>a>>n;
    euclid_extins (a,n);
    if (x<=0)
        x+=n;
    fout<<x;
    return 0;
}