#include <cstdio>

using namespace std;

#define FILEIN "inversmodular.in"
#define FILEOUT "inversmodular.out"

void euclidext(int a, int b, int& d, int& x, int& y) {
    if (b == 0) {
        d = a;
        x = 1;
        y = 0;
        return;
    }

    int x0, y0;
    euclidext(b, a%b, d, x0, y0);
    x = y0;
    y = x0 - (a / b) * y0;
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    int a, n, d, x, y;

    scanf("%d %d", &a, &n);

    euclidext(a, n, d, x, y);

    while (x < 0)
        x += n;

    printf("%d\n", x);

    return 0;
}