#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int s(int a, int b, int& x, int& y)
{
	if (b == 0) { x = 1, y = 0; return a; }
		int x0, y0,d;
		d=s(b, a % b, x0, y0);
		x = y0;
		y = x0 - (a / b) * y0;
		return d;
}
int main()
{
	int a, n;
	fin >> a >> n;
		int d,x,y;
	d = s(a, n, x, y);
	while (x < 0)
		x += n;
	fout << x;
	return 0;
}