#include <fstream>

using namespace std;

int main() 
{
	ifstream cin("test.in");
	ofstream cout("test.out");
	int a, n;
	cin >> a >> n;
	pair<int,int> t = make_pair(0,1);
	pair<int,int> r = make_pair(n,a);  
	while (r.second != 0) {
		int quotient = r.first / r.second;
		t = make_pair (t.second, t.first - quotient * t.second);
		r = make_pair (r.second, r.first - quotient * r.second);
	}

	if (r.first > 1) cout << "a is not invertible";
	if (t.first < 0) t.first += n;
	cout << t.first;
	return 0;
}