#include <fstream>

using namespace std;

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

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

void getFactors(int a, int b, int &gcd, int &x, int &y) {
	//
	if (b == 0) {
		gcd = a;
		x = 1; 
		y = 0;
	}
	else {
		getFactors(b, a % b, gcd, 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, gcd = 0;
	getFactors(n, a, gcd, x, y);
	
	inv = y;
}

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

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