#include <fstream>

using namespace std;

void gcd(int a, int b, int& x, int& y) {
	if (!b) {
		x = 1;
		y = 0;
	} else {
		int x0, y0;
		gcd(b, a % b, x0, y0);
		x = y0;
		y = x0 - a / b * y0;
	}
}

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

	int A, N;

	fin >> A >> N;

	int inv, y;

	gcd(A, N, inv, y);

	while (inv < 0)
		inv += N;

	fout << inv;

	return 0;
}