#include <fstream>

using namespace std;

int A, N, x, y;

void valoare(int a, int b, int &x, int &y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return;
	}
	int xa, ya;
	valoare(b, a%b, xa, ya);
	x = ya;
	y = xa - (a / b)*ya;
}

int main() {
	ifstream f("inversmodular.in");
	ofstream g("inversmodular.out");
	f >> A >> N;
	valoare(N, A, x, y);
	if (y<0)
		y = (y + N*((0 - y) / N + 1)) % N;
	g << y << "\n";
	return 0;
}