#include<cstdio>

long long a,n,x,y;

void gcd(long long a,long long b,long long &x,long long &y)
{
	if(!b)
		x=1 , y=0;
	else
	{
		gcd(b,a%b,x,y);
		long long aux = x;
		x = y;
		y = aux - y*(a/b);
	}
}

int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%lld %lld",&a,&n);
	gcd(a,n,x,y);
	x =(n+x%n)%n;
	printf("%lld",x);
	fclose(stdout);
	return 0;
}