#include <fstream>
using namespace std;

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

int A, N, X, Y;

void euclid (int a, int b)
{
	if (b == 0)
	{
		X = 1;
		Y = 0;
	}
	else
	{
		euclid (b, a % b);
		int x = X, y = Y;
		X = y;
		Y = x - (a / b) * y;
	}	
}

int main ()
{
	fi >> A >> N;
	euclid (A, N);
	if (X < 0) X = X % N + N;
	fo << X << '\n';
	return 0;
}