#include <iostream>
#include <fstream>

using namespace std;
#define LL long long int
ifstream fi("inversmodular.in");
ofstream fo("inversmodular.out");
LL x, y, d;
void euclide(LL a, LL b, LL& x, LL& y, LL& d)
{
	if (b == 0)
	{
		a = d;
		x = 1;
		y = 0;
		return;
	}
	LL x1, y1, q = a / b;
	euclide(b, a%b, x1, y1, d);
	x = y1;
	y = x1 - y1*q;
}

int main()
{
	LL A, N, X;
	fi >> A >> N;
	euclide(A, N, x, y, d);
	if (x < 0)
	{
		while (x < 0)
			x += N;
	}
	fo << x;
	return 0;
}