#include <cstdio>

void extended_euclid (const int &a, const int &b, int &x, int &y) {

    if (!b) {
        x = 1;
        y = 0;
        return;
    }
    int _x, _y;
    extended_euclid (b, a % b, _x, _y);
    x = _y;
    y = _x - a / b * _y;

}

inline int modular_inverse (const int &N, const int &M) {

    int x, y;
    extended_euclid (N, M, x, y);
    if (x < 0) {
        x += (-x / M + 1) * M;
    }
    return x;

}

int main () {

    freopen ("inversmodular.in", "r", stdin);
    freopen ("inversmodular.out", "w", stdout);
    int a, b;
    scanf ("%d%d", &a, &b);
    printf ("%d", modular_inverse (a, b));

}