#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,avx,fma,avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;
using ll = long long;

/* a*x + b*y = 1 ---> {x, y} */
pair<ll, ll> euclid(int a, int b) {
	if (b == 0)
		return {1, 0};

	pair<ll, ll> p = euclid(b, a % b);
	return {p.second, p.first - (a / b) * p.second};
}

void solve()
{
	int a, b;
	cin >> a >> b;

	pair<ll, ll> p = euclid(a, b);

	cout << (p.first + b * 1LL * INT_MAX) % b << '\n';
}

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

	// #ifndef ONLINE_JUDGE
    // freopen("input.in", "r", stdin);
    // freopen("output.out", "w", stdout);
    // #endif

	int t = 1;
	// cin >> t;
	while(t--)
		solve();

	return 0;
}