#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

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

void euclid_ext(int a, int b, int &x0, int &y0)
{
	if (b)
	{
		int x1, y1;

		euclid_ext(b, a%b, x1, y1);

		x0 = y1;
		y0 = x1 - y1*(a / b);
	}
	else
		x0 = 1, y0 = 0;
}

int main()
{
	
	int a, x;

	in >> a >> x;

	int c, v;

	euclid_ext(a, x, c, v);

	while (c < 0)
		c += x;

	out << c;

	return 0;


}