#include <bits/stdc++.h>

typedef long long LL;

std::pair<LL, LL> xgcd(LL a, LL b, LL& d) {
	if(!b) {
		d = a;
		return {1, 0};
	}

	auto result = xgcd(b, a % b, d);

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

int main() {
	std::ifstream in("../inversmodular.in");
	std::ofstream out("../inversmodular.out");

    LL a, n, d;
    in >> a >> n;
	auto result = xgcd(a, n, d);

	LL invers = result.first;

	while(invers < 0) invers += n;

	out << invers;


	return 0;

}