#include <fstream>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

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

int main()
{
	int A, N;
	long long inv, ins;
	in >> A >> N;
	gcd(inv, ins, A, N);
	if (inv <= 0) inv += N;
	out << inv;
	return 0;
}