#include <cstdio>

using namespace std;
typedef long long LL;
LL gcd(LL &x, LL &y, LL a, LL b) {
	if (b==0) {x=1; y=0; return a;}
	gcd(x, y, b, a % b);
	LL aux = x;
	x = y;
	y = aux - y * (a / b);
}
int main() {
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);
	LL inv, inv2;
	LL A, N;
	scanf("%lld %lld", &A, &N);
	gcd(inv, inv2, A, N);
	inv = (N + inv) % N;
	printf("%lld\n", inv);
	return 0;
}