#include <cstdio>

long long a, b, x, y;

inline void read (void)
{
	std::freopen("inversmodular.in","r",stdin);
	std::scanf("%lld%lld",&a,&b);
	std::fclose(stdin);
}

inline void print (void)
{
	std::freopen("inversmodular.out","w",stdout);
	std::printf("%lld\n",x);
	std::fclose(stdout);
}

void Euclid (long long a, long long b, long long &x, long long &y)
{
	if (!b)
	{
		x = 1;
		y = 0;
		return;
	}
	long long x0, y0;
	Euclid(b,a % b,x0,y0);
	x = y0;
	y = x0 - (a / b) * y0;
}

int main (void)
{
	read();
	Euclid(a,b,x,y);
	if (x <= 0)
		x = b + (x % b);
	print();
	return 0;
}