#include <fstream>
#include <stdio.h>

#define ll long long

void euclid_extins(int a, int b, ll &x, ll &y) {
	if (b == 0) {
		x = 1;
		y = 0;
	} else {
		euclid_extins(b, a % b, x, y);
		ll temp = x;
		x = y;
		y = temp - (a / b) * y;
	}
}

int main() {
	// std::ifstream cin("inversmodular.in");
	// std::ofstream cout("inversmodular.out");
	// std::ios::sync_with_stdio(false);
	freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);

	int a, n;
	ll inv = 0, y;

	//cin >> a >> n;
	scanf("%d%d", &a, &n);
	euclid_extins(a, n, inv, y);

	if (inv <= 0) {
		inv = n + inv % n;
	}

	printf("%lld\n", inv);
	//cout << (ll)inv << '\n';

	return 0;
}