#include <cstdio>

using namespace std;

void euclid_extins (long long a, long long n, long long &x, long long &y) {
	long long c, xx, yy;
	if (a == 0) {
		x = 0; y = 1;
		return;
	}
	euclid_extins (n % a, a, xx, yy);
	y = xx;
	x = yy - xx * (n / a);
}

int main () {
	long long a, n, x, y;
	freopen ("inversmodular.in", "rt", stdin);
	freopen ("inversmodular.out", "wt", stdout);
	scanf ("%lld%lld", &a, &n);
	euclid_extins (a % n, n, x, y);
	printf ("%d\n", x);
	return 0;
}