#include<iostream>
#include<fstream>
using namespace std;

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

int T,a,b,c,x,y,cm;

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

int main()
{
		in >> a >> b;
		cmmdc(a, b, x, y,cm);
		while (x < 0)
			x += b;

		out << x;

	in.close();
	out.close();
	return 0;
}