#include<cstdio>
#include<fstream>

using namespace std;

#define l long long

int a,n;

inline void euclid (int a,int b,l &x,l &y)
{

if(b==0){
y=0;
x=1;
}
else{

euclid(b,a%b,x,y);
l aux=x;
x=y;
y=aux-(a/b)*y;
}

}

int main ()
{

ifstream in ("inversmodular.in");
freopen("inversmodular.out","w",stdout);

in>>a>>n;
in.close();
l x,y;
euclid (a,n,x,y);
if(x<=0)
x=n+x/n;

printf("%lld\n",x);


return 0;}