#include <cstdio>

int gcd_extended(int a,int b,int *x,int *y)
{
	if (b == 0)
	{
		*x = 1;
		*y = 0;
		return a;
	}
	else
	{
		int x0,y0,d;
		d = gcd_extended(b,a%b,&x0,&y0);
		*x = y0;
		*y = x0-(a/b)*y0;
	}
}

int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	int a,n;
	int x,y;
	scanf ("%d%d",&a,&n);

	int d = gcd_extended(a,n,&x,&y);

	while (x<0) x+=n;
	x%=n;
	printf ("%d\n",x);
	return 0;
}