#include <cstdio>

#define ll long long

ll a, n;

void euclid(ll a, ll b, ll *x, ll *y)
{
    if (b == 0)
    {
	*x = 1;
	*y = 0;

	return ;
    } 
    ll x0, y0;
    euclid(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;
    euclid(a, n, &x, &y);
    while (x < 0) x += n;
    printf("%lld\n", x);

    return 0;
}