#include<fstream>
using namespace std;

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

int n, a;

void gcd(int a, int b, long long& x, long long& y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
	}
	else
	{
		gcd(b, a % b, x, y);
		long long temp = x;
		x = y;
		y = temp - y * (a / b);
	}
}
int main()
{
	f >> a >> n;
	long long x, y;
	gcd(a, n, x, y);
	if (x <= 0)
		x = n + x % n;
	g << x;
}