#include <iostream>
#include <fstream>
#define long long int int

using namespace std;

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

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

int a, b, d, x, y;

int main()
{
	f >> a >> b;
	euclid(a, b, d, x, y);
	while (x < 0)
		x += b;
	g << x;
	return 0;
}