#include <cstdio>
using namespace std;

int d;

void euclid (int a, int b, int &x, int &y) {

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

}

int main () {

    freopen ("inversmodular.in", "r", stdin);
    freopen ("inversmodular.out", "w", stdout);
    int a, n, x, y;
    scanf ("%d %d", &a, &n);
    d = 1;
    euclid (a, n, x, y);
    if (x < 0)
        x += (-x / n + 1) * n;
    printf ("%d", x);

}