#include<cstdio>

void euclid(int a,int b,int &d,int &x,int &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		d=a;
		return;
	}
	int xx,yy,q=a/b;
	euclid(b,a%b,d,xx,yy);
	x=yy;
	y=xx-q*yy;
}

inline int prel(int x,int n)
{
	return x%n >= 0 ? x%n : n+x%n;
}

int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	int a,n,x,y,d;
	scanf("%d%d",&a,&n);
	euclid(a,n,d,x,y);
	printf("%d\n",prel(x,n));
	return 0;
}