#include <cstdio>

using namespace std;

void gcd(int x, int y, int &a, int &b) {
    if(y == 0) {
        a = 1;
        b = 0;
    } else {
        gcd(y, x % y, a, b);
        int backup = a;
        a = b;
        b = backup - b * (x / y);
    }
}

int main() {
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);

    int a, n, x, y;
    scanf("%d%d", &a, &n);
    gcd(a, n, x, y);
    while(x < 0)
        x += n;
    printf("%d\n", x);

    return 0;
}