#include<fstream>
#include<algorithm>
#include<string.h>
using namespace std;

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

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

}

int main()
{
	int r, x, y,a,b;
	in >> a >> b;
	euclid_extins(a, b, x, y, r);
	out << x%b;
		
	return 0;
}