#include <fstream>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

int euclid(const int& a, const int& b, int& x, int& y) {
    if(!b) {
        x = 1;
        y = 0;
        return a;
    }
    int xNew, yNew;
    int e = euclid(b, a % b, xNew, yNew);

    x = yNew;
    y = xNew - yNew * (a / b);

    return e;
}

int main() {
    int a, n, x, y;
    f>>a>>n;
    f.close();

    euclid(a, n, x, y);
    while(x <= 0) {
        x = n + x % n;
    }
    g<<x<<'\n';
    g.close();

    return 0;
}