#include <fstream>
using namespace std;

ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");

typedef long long i64;

i64 a, n, inv, irelev;

void euclid(i64 a, i64 b, i64 &x, i64 &y) {
	if (!b) {
		x = 1, y = 0;
		return;
	}
	i64 x0, y0;
	euclid(b, a % b, x0, y0);
	x = y0;
	y = x0 - (a / b) * y0;
}

int main() {
	fin >> a >> n;
	fin.close();
	euclid(a, n, inv, irelev);
	if (inv <= 0)
		inv = n + inv % n;
	fout << inv;
	fout.close();
	return 0;
}