#include <fstream>
#define ll long long
using namespace std;
long long a,N,inv,ins;
ll gcd(ll a,ll b,ll &x,ll &y)
{
   ll x0=0,y0=0,d=0;
   if (!b) {x=1;y=0;return a;}
   d=gcd(b,a%b,x0,y0);
   x=y0;
   y=x0-(a/b)*y0;
   return d;
}
int main()
{
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");
    f>>a>>N;
    gcd(a,N,inv,ins);
    if (inv<=0) g<<inv+N;else g<<inv;
    f.close();
    g.close();
    return 0;
}