# include <fstream>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

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

    int xs, ys, d;
    d = euclid(b, a%b, xs, ys);
    x = ys;
    y = xs - (a/b) * ys;
    return d;
}

// inversModular(A, N) = inversul modular al lui A modulo N
int inversModular(int A, int N) {
    int X, Y;
    if (euclid(A, N, X, Y))
        ;

    while (X < 0)
        X += N;

    return X;
}

int A, N;

int main() {
    fin >> A >> N;

    fout << inversModular(A, N);

    return 0;
}