#include <fstream>
using namespace std;

int a, b;
long long inv, x;

void Citire() {
    ifstream in("inversmodular.in");
    in >> a >> b;
    in.close();
}

void Euclid( long long &inv, long long &x, int a, int b) {
    if (!b) {
        inv = 1;
        x = 0;
        return;
    }
    Euclid(inv, x, b, a%b);
    long long aux = inv;
    inv = x;
    x = aux - x * (a / b);
}

void Solve() {
    Euclid(inv, x, a, b);
    while (inv < 0)
        inv += b;
}

void Afisare() {
    ofstream out ("inversmodular.out");
    out << inv << '\n';
    out.close();
}

int main() {
    Citire();
    Solve();
    Afisare();
    return 0;
}