#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{
l xx,yy;
euclid(b,a%b,xx,yy);
x=yy;
y=xx-(a/b)*yy;
}

}

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+=((x/n+1)*n);

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


return 0;}