#include <iostream>
#include <fstream>

using namespace std;

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

void gcdExtended(int n, int a, int& x, int& y)
{
	if (n % a == 1)
	{
		x = 1;
		y = -1;
		return;
	}

	int x1, y1;
	gcdExtended(a, n % a, x1, y1);

	x = y1;
	y = x1 - (n / a) * y1;
}

int invMod(int n, int a)
{
	int x, y;
	gcdExtended(n, a, x, y);
	return (1ll * y + n) % n;
}

int main()
{
	int a, n;
	fin >> a >> n;
	fout << invMod(n, a);
	return 0;
}