# 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;
}

int A, N, X, Y;
int main() {
    fin >> A >> N;

    if (euclid(A, N, X, Y))
        fout << X;

    return 0;
}