#include <cstdio>
#include <cassert>
#include <algorithm>
#define _submit
#ifdef _submit
#define InFile "inversmodular.in"
#define OtFile "inversmodular.out"
#else
#define InFile "fis.in"
#define OtFile "fis.out"
#endif

typedef long long LL;

class pair {
public:
	LL x, y;
	pair operator*(LL a) {
		return{ x*a, y*a };
	}
	pair operator-(pair p2) {
		return{ this->x - p2.x, this->y - p2.y };
	}
};

pair euclidExtins(LL a, LL b, LL c) {
	pair s = { 1, 0 }, t = { 0, 1 };
	while (b) {
		LL q = a / b;
		LL r = a % b;
		pair pr = s - t*q;
		a = b;
		b = r;
		s = t;
		t = pr;
	}
	if (c % a)
		return{ 0, 0 };
	return s*(c / a);
}

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OtFile, "w", stdout));
	int A, B;
	scanf("%d%d", &A, &B);
	LL sol = (int)euclidExtins(A, B, 1).x;
	sol %= (LL)B;
	if (sol < 0)
		sol += B;
	printf("%d\n", (int)sol);
	return 0;
}