# include <stdio.h>
int n,a,b,c,d,x0,y0,i;
long long x, y;
void algee(int a, int b, long long &x, long long &y)
{
	if (b==0)
	{
		x=1;
		y=0;
	}
	else
	{
	algee(b,a%b,x,y);
	long long aux =x;
	x=y;
	y=aux-(a/b)*y;
	}
}
int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%d %d\n",&a,&n);
	
	algee(a,n,x,y);
	while (x<0) x=n+x%n;
	printf("%lld\n",x);
	return 0;
}