#include <fstream>
#define ll long long int

using namespace std;

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

int a, n;

void cmmdc(ll &invers, ll &ins, int a, int b)
{
	if (!b)
		invers = 1, ins = 0;
	else
	{
		cmmdc(invers, ins, b, a % b);
		ll aux = invers;
		invers = ins;
		ins = aux - ins * (a / b);
	}
}

int main()
{
	ll invers = 0, ins;

	in >> a >> n;
	cmmdc(invers, ins, a, n);

	if (invers <= 0) invers = n + invers % n;

	out << invers;

    return 0;
}