#include <fstream>

int gcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1;
        y = 0;
        return a;
    }
    int ax, ay;
    int aux = gcd(b, a % b, ax, ay);
    x = ay;
    y = ax - (a / b) * ay;
    return aux;
}

int main()
{
    std::ifstream in("inversmodular.in");
    std::ofstream out("inversmodular.out");
    int a, n, x, y;
    in >> a >> n;
    gcd(a, n, x, y);
    if (x <= 0)
    {
        x = n + x % n;
    }
    out << x << '\n';
    in.close();
    out.close();
    return 0;
}