#include<stdio.h>
#define tip long long
tip a,n,x,y;
void read(),solve(),invmod(tip a,tip b,tip &x,tip &y);
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%lld%lld",&a,&n);
}
void solve()
{
	invmod(a,n,x,y);
	while(x<0)x+=n;
	printf("%lld\n",x);
}
void invmod(tip u,tip v,tip &x,tip &y)
{
	if(!v){x=1;y=0;return;}
	tip X,Y;invmod(v,u%v,X,Y);x=Y;y=X-(u/v)*Y;	
}