#include <stdio.h>


long long k, a, n, ok, x, y;


void gcd(long long &x, long long &y, long long a, long long b)

{
	if (b == 0)
	{
		x = 1;
		y = 0;
	}
	else
	{
		gcd(x, y, b, a%b);
		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(x, y, a, n);

/*	ok = 0;
	for (k=0; (k*n+1) < a; ++k);
	while (!ok)
	{
		if ( ((k*n)+1) % a == 0)
		{
			ok = 1;
			x = ((k*n)+1)/a;
		}
		++k;
	}
*/
	if (x <= 0)
	{
		x = (n+x) % n;
	}

	printf("%lld\n", x);

	return 0;
}