#include <fstream>
using namespace std;
long long a, b, aux;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
int main() {
	cin >> a >> b;
	aux = b;
	long long r;
	pair<long long, long long>per1, per2;
	per1 = { 1, 0 };
	per2 = { 0, 1 };
	long long x, y, c;
	while (b != 0) {
		r = a % b;
		c = a / b;
		a = b;
		b = r;
		pair<long long, long long> auxi;
		auxi.first = per1.first - c * per2.first;
		auxi.second = per1.second - c * per2.second;
		per1 = per2;
		per2 = auxi;
	}
	x = per1.first;
	y = per1.second;
	if (x <= 0) {
		x = aux + x % aux;
	}
	cout << x;
}