#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL a, n, d;

pair<LL, LL> euclid(LL a, LL b) {
	if(!b) {
		d = a;
		return {1, 0};
	}

	auto result = euclid(b, a % b);
	return { result.second, result.first - (a / b) * result.second };
}

void citire() {
	scanf("%lld %lld", &a, &n);
}

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

	citire();
	auto result = euclid(a, n);
	
	LL invers = result.first;

	while(invers < 0) invers += n;

	printf("%lld", invers);


	return 0;
}