#include <fstream>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
void ex(int a,int b,int &x, int &y)
{
	if(!b)
	{
		x=1;
		y=0;
	}
	else
	{
		int x0,y0;
		ex(b,a%b,x0,y0);
		x=y0;
		y = x0 -(a/b)*y0;
	}
}
int main ()
{
	int a,b;
	in>>a>>b;
	int x,y;
	ex(a,b,x,y);
	if(x<0)
		x+=b;
	out<<x;
	return 0;
}