#include <stdio.h>

long long a, n;

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

int main()
{
	long long inv=0, ins;
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);
	scanf("%lld %lld\n", &a, &n);
	gcd(&inv, &ins, a, n);
	if (inv<0)
		inv=n+inv%n;
	printf("%lld\n", inv);
	return 0;
}