#include <fstream>
#include <list>
#include <utility>

using namespace std;

long long inverseMod(const long long A, const long long B) {
    long long a = A, b = B;
    list<pair<long long, long long>> coefStack;

    while (b) {
        coefStack.push_back({a, b});
        long long temp = a;
        a = b;
        b = temp % b;
    }

    long long x1 = 1LL, y1 = 0LL;
    long long x, y, q;

    while (!coefStack.empty()) {
        auto &cf = coefStack.back();
        coefStack.pop_back();
        a = cf.first;
        b = cf.second;
        q = a / b;

        x = y1;
        y = x1 - q * y1 * 1LL;

        x1 = x;
        y1 = y;
    }

    if (x < 0LL) {
        long long positiveX = -x;

        q = positiveX / B;
        if (positiveX % B)
            ++q;

        x += q * B * 1LL;
    }
    return x;
}

int main(void) {
    ifstream in("inversmodular.in");
    ofstream out("inversmodular.out");

    int a, n;
    in >> a >> n;

    out << inverseMod(a, n);

    in.close();
    out.close();
    return 0;
}