#include <fstream>

using namespace std;

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

int x, y, a, n;

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

    int x1, y1, d = Euclid_E(b, a % b, x1, y1);

    x = y1;
    y = x1 - y1 * (a / b);

    return d;
}

int main() {
    fin >> a >> n;
    Euclid_E(a, n, x, y);

    while(x <= 0) x += n;

    fout << x << '\n';

    return 0;
}