#include <fstream>

#define input "inversmodular.in"
#define output "inversmodular.out"

using namespace std;
typedef long long ll;

ifstream in(input);
ofstream out(output);

void Euclid_Extins(ll A, ll B, ll &x, ll &y)
{
	if (!B)
	{
		x = 1;
		y = 0;
	}
	else
	{
		ll x0 = 0, y0 = 0;
		Euclid_Extins(B, A % B, x0, y0);
		x = y0;
		y = x0 - y0 * (A / B);
	}
}

void Read_Data()
{
	ll A, N, X = 0, Y = 0;
	in >> A >> N;
	Euclid_Extins(A, N, X, Y);
	while (X < 0)
		X += N;
	out << X;
}

int main()
{
	Read_Data();
	return 0;
}