#include <bits/stdc++.h>
#define int long long
int a, n;
void cmmdc (int a, int b, int &x, int &y) { /// geeks for geeks time
        int x0, y0;
        if (b == 0)
        { x = 1, y = 0; }
        else {
                cmmdc (b, a % b, x0, y0);
                x = y0;
                y = x0 - (a / b) * y0;
        }
}
int32_t main() {
        int x, y;
        freopen ("inversmodular.in", "r", stdin);
        freopen ("inversmodular.out", "w", stdout);
        scanf ("%d %d", &a, &n);
        cmmdc (a, n, x, y);
        printf ("%d", ( (x % n) + n) % n);
        return 0;
}