#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);

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

	cin >> a >> n;
	euclid_extins(a, n, inv, y);

	if (inv <= 0) {
		inv = n + inv % n;
	}
	
	cout << (ll)inv << '\n';

	return 0;
}