#include <fstream>
using namespace std;

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

pair <int, int> euclid(int x, int y) {
    if (y == 0) return {1, 0};
    auto p = euclid(y, x % y);
    return {p.second, p.first - 1ll * (x / y) * p.second};
}

int main() {
    int a, n;

    in >> a >> n;

    auto q = euclid(a, n);
    while (q.first < 0)
        q.first += n;

    out << q.first;

    return 0;
}