#include <fstream>
using namespace std;

pair<int,int> bezout(int a, int b) {
	if (a == 0) return pair<int,int>(0,b);
	pair<int,int> c = bezout(b%a,a);
	return pair<int,int> (c.second-b/a*c.first,c.first);
}

int main() {
	ifstream fin("inversmodular.in");
	ofstream fout("inversmodular.out");
	int a, n;
	fin >> a >> n;
	int b = bezout(a,n).first%n;
	if (b < 0) b += n;
	fout << b;
	return 0;
}