#include <fstream>

using namespace std;

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

int euclidextins(int a, int b, int &x, int &y);
int cmmdc(int a, int b);

int main()
{
	int a, n, x, ceva;
	fin >> a >> n;
	euclidextins(a, n, x, ceva);
	while (x < 0)
        x += n;
    fout << x << '\n';
    return 0;
}

int euclidextins(int a, int b, int &x, int &y)
{
	int d, x1, y1;
	if (b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	d = euclidextins(b, a % b, x1, y1);
	x = y1;
	y = x1 - (a / b) * y1;
	return d;
}

int cmmdc(int a, int b)
{
	if (b == 0)
		return a;
	return cmmdc(b, a % b);
}