#include <bits/stdc++.h>

#define llg     long long

#define FILENAME    std::string("inversmodular")
std::ifstream input (FILENAME+".in");
std::ofstream output(FILENAME+".out");

int gcd(llg A, llg B, llg &X, llg &Y) {
    if (B == 0) {
        X = 1;
        Y = 0;
        return A;
    }   int v = gcd(B, A%B, X, Y);
    llg aux = Y;
    Y = X - (A/B)*Y;
    X = aux;
    return v;
}

int main()
{
    llg A, B;   input >> A >> B;
    llg X, Y;   gcd(A, B, X, Y);
    output << (X%B+B)%B;

    return 0;
}