# include <bits/stdc++.h>

using namespace std;

long long a, n, aux, r, c, y1, y0, y;

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

    scanf("%lld %lld\n", &a, &n);

    aux = n, y1 = 1;
    while (a) {
        r = n % a, c = n / a;
        n = a, a = r;
        y = y0 - c * y1;
        y0 = y1, y1 = y;
    }

    while (y0 < 0)
        y0 += aux;

    printf("%lld\n", y0);

    return 0;
}