#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll n, a;
int i;

void inversmodular(ll a,ll b,ll &x, ll &y)
{
	if (!b) x = 1, y = 0;
	else
	{
		ll x0, y0;
		inversmodular(b, a % b, x0, y0);
		x = y0;
		y = x0 - (a / b) * y0;
	}
}

int main()
{
	freopen ("inversmodular.in","r",stdin);
	freopen ("inversmodular.out","w",stdout);

	scanf("%lld%lld", &a, &n);
	
	ll x,y;
	inversmodular(a,n,x,y);

	if (x <= 0) x = n + x % n;
	printf("%lld", x);
	return 0;
}