#include <bits/stdc++.h>
#define LL long long

using namespace std;

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

pair<LL, LL> euclid(LL a, LL b) {
    if (b == 0)
        return {1, 0};
    auto p = euclid(b, a % b);
    return {p.second, p.first - p.second * (a / b)};
}

int main() {
    LL a, n;
    fin >> a >> n;
    auto res = euclid(a, n);
    if (res.first <= 0)
        res.first = n + res.first % n;
    fout << res.first;
    return 0;
}