#include <fstream>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

void readNumbers(int &a, int &n) {
	//
	f >> a >> n;
}

int computeGcd(int a, int b) {
	//
	while (a % b) {
		//
		int aux = a;
		a = b;
		b = aux % b;
	}

	return b;
}

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

void computeModularMultiplicativeInverse(int a, int n, int &inv) {
	int x = 0, y = 0;
	int gcd = computeGcd(a, n);

	getFactors(n / gcd, a / gcd, x, y);
	while (y < 0) y += n;
	inv = y;
}


int main() {
	//
	int a, n, inv;

	readNumbers(a, n);
	computeModularMultiplicativeInverse(a, n, inv);
	g << inv;
}