#include <fstream>
using namespace std;

void euclid(long x, long * y, long n, long * m);

long main(){
	ifstream in("inversmodular.in");
	long x, y, n, m;
	in >> x >> n;
	euclid(x, &y, n, &m);
	ofstream out("inversmodular.out");
	out << (y % n + n) % n;
	return 0;
}

void euclid(long x, long * y, long n, long * m){
	if (x == 0){
		*y = 0;
		*m = 1;
	}
	else{
		long y0, m0;
		euclid(n % x, &y0, x, &m0);
		*m = y0;
		*y = m0 - (n - (n % x)) / x * y0;
	}
}