#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

long long a,b,x,y,d,t,i,c,n;

void euclid_ext (long long a, long long b, long long &x, long long &y)
{
    if(b==0) { x=1; y=0;}
    else{

    long long xp=0, yp=0;

    euclid_ext(b, a%b, xp, yp);

    x=yp;
    y=xp-(a/b)*yp;

    }
}

int main()
{

    fin>>a>>n;

    euclid_ext(a, n, x, y);

    if(x>=0)
    fout<<x;
    else { x=x-n*(x/n);
    x=x+n;

    fout<<x;}


    return 0;
}