#include <cstdio>

int A, N;

void extendedEuclid(int A, int B, int& resultX, int& resultY) {
	if (B == 0) {
		resultX = 1;
		resultY = 0;
		return;
	}

	int prevResultX, prevResultY;
	extendedEuclid(B, A % B, prevResultX, prevResultY);

	resultX = prevResultY;
	resultY = prevResultX - (A / B) * prevResultY;
}

inline int positiveMod(int x, int MOD) {
	x %= MOD;
	if (x < 0) {
		x += MOD;
	}

	return x;
}

int main() {
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);

	scanf("%d%d", &A, &N);
	// A * x + N * y = cmmdc(A, N) = 1
	int x, y;
	extendedEuclid(A, N, x, y);

	printf("%d\n", positiveMod(x, N));

	return 0;
}