#include <iostream>
#include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

void euclid(int a, int b, int* x, int* y)
{
	if (b == 0)
	{
		*x = 1;
		*y = 0;
	}
	else
	{
		int x0, y0;
		euclid(b, a % b, &x0, &y0);
		* x = y0;
		*y = x0 - a / b * y0;
	}



}


int main()
{
	int a, b, d, x, y;

	f >> a >> b;
	 d = 0;
	euclid(a, b, &x, &y);
	if (x < 0)
	{
		int aux = -x/b;
		x = x + aux * b;
		if (x < 0) x += b;
	}
	g << x;




	return 0;

}