#include <iostream>
#include <fstream>

using namespace std;

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

int a, n, x, y;

int gcd_extins(int a, int b)
{	if(!b)
		{	x = 1;
			y = 0;
			return a;
		}
	int gcd = gcd_extins(b, a % b), x1 = y, y1 = x - y * (a / b);
	x = x1;
	y = y1;
	return gcd;
}

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