#include <fstream>
using namespace std;

pair<int, int> eucl_ext(int a, int b)
{
	if (b == 0)
		return { 1, 0 };
	auto p = eucl_ext(b, a % b);
	return { p.second,  p.first - a / b * p.second };
}

int main()
{
	ifstream f("inversmodular.in");
	ofstream g("inversmodular.out");
	int x, y;
	f >> x >> y;
	int inv = eucl_ext(x, y).first;
	if (inv < 0) inv += y;
	g << inv;
	return 0;
}
/*
(a, b) = d            |
ak + bl = d           |  ak + bl = bk' + (a % b)l'  |										|k = l'
(b, a % b) = d        |                             | => ak + bl = bk' + al' - bl'[a/b] =>  |l = k' - l'[a/b]
bk' + (a % b)l' = d   |                             |
a = b * [a / b] + a % b => a % b = a - b * [a / b]  |

*/