#include <iostream>
#include <fstream>

using namespace std;

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

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

	int x1, y1;
	int gcd = gcdExtended(b % a, a, x1, y1);

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

	return gcd;
}

int invMod(int a, int b)
{
	int x, y;
	int gcd = gcdExtended(a, b, x, y);
	return (x + b) % b;
}

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