# 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;
}