#include <cstdio>
using namespace std;

typedef long long ll;
ll a, n, d, x, y;

ll gcd(ll a, ll b, ll &x, ll &y)
{
	if(!b)
	{
		x = 1, y = 0;
		return a;
	}

	ll x1, y1;
	ll d = gcd(b, a%b, x1, y1);

	x = y1;
	y = x1 - (a / b) * y1;

	return d;
}

int main()
{

	scanf("%lld%lld", &a, &n);
	d = gcd(a, n, x, y);

	if(x <= 0)
		x = n + x % n;

	printf("%lld", x);

	return 0;
}