#include <fstream>

using namespace std;

int A, N;

void Euclid_Extins(long long &x, long long &y, int a, int b)
{
	if (!b)
	{
		x = 1;
		y = 0;
	}
	else
	{
		Euclid_Extins(x, y, b, a%b);
		long long aux = x;
		x = y;
		y = aux - y%(a/b);
	}
}

int main()
{
	ifstream f("inversmodular.in");
	ofstream g("inversmodular.out");
	f>>A>>N;
	f.close();
	long long x, y;
	Euclid_Extins(x, y, A, N);
	if (x<=0)
		x = N + x%N;
	g<<x<<"\n";
	g.close();
	return 0;
}