#include<cstdio>
void read(),solve();
int A,N,D,cmmdc(int A,int B,long long &X,long long &Y);
long long X,Y;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%d%d",&A,&N);
}
void solve()
{
	D=cmmdc(A,N,X,Y);
	for(;X<0;X+=N);
	printf("%lld\n",X);
}
int cmmdc(int A,int B,long long &X,long long &Y)
{
	if(!B)
	{
		X=1;
		Y=0;
		return A;
	}
	long long x0,y0;int d;
	d=cmmdc(B,A%B,x0,y0);
	X=y0;
	Y=x0-(A/B)*y0;
	return d;
}