#include <iostream>
#include <fstream>

using namespace std;

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

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

	int x1, y1;
	int gcd = gcdExtended(n % a, a, x1, y1);
	
	x = y1 - x1 * (n / a);
	y = x1;
	return gcd;
}

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

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