#include <fstream>
using std::pair;

int a, n;

std::ifstream in("inversmodular.in");
std::ofstream out("inversmodular.out");

pair<long long, long long> euclid_extended(int x, int y)
{
	if (y == 0)
		return { 1,0 };
	auto p = euclid_extended(y, x%y);
	return { p.second, p.first - (x / y)*p.second };
}


int main(void) {
	std::ios::sync_with_stdio(false);

	in >> a >> n;

	auto x = euclid_extended(a, n).first;

	while (x < 0) x += n;

	out << x;
}