#include<cstdio>
long long x,y;
void eucl(long long  a,long long b){
	if(!b){
		x=1;
		y=0;
		return;
	}
	eucl(b,a%b);
	int tmp=y;
	y=x-(a/b)*y;
	x=tmp;
}
int main()
{
	freopen ("inversmodular.in","r",stdin);
	freopen ("inversmodular.out","w",stdout);
	int a,n;
	scanf ("%d%d",&a,&n);
	eucl (a,n);
	while(x<0)x+=n;
	printf ("%d",x);
	return 0;
}