#include <fstream>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
void gcd(long long  a, long long b, long long& d, long long& k, long long& l)
{
	if (!b)
	{
		d = a;
		k = 1;
		l = 0;
	}
	else
	{
		long long lnou, knou;
		gcd(b, a % b, d, knou, lnou);
		k = lnou;
		l = knou - (a / b) * lnou;
	}
}
int main()
{
	long long a, b;
	cin >> a >> b;
	long long k, l, d;
	gcd(a, b, d, k, l);
	while (k < 0)
		k += d;
	cout << k;
	return 0;
}