#include <fstream>

using namespace std;

pair<int, int> Euclid(int a, int b)
{
    if (b == 0) {
        return {1, 0};
    }

    auto prev = Euclid(b, a % b);
    auto x = prev.second;
    auto y = prev.first - (a / b) * prev.second;
    return {x, y};
}

int ModInv(int a, int b)
{
    auto inv = Euclid(a, b).first;
    while (inv < 0) {
        inv += b;
    }
    return inv;
}

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

    int a, b;
    fin >> a >> b;

    auto inv = ModInv(a, b);
    fout << inv << "\n";

    return 0;
}