#include <bits/stdc++.h>

using namespace std;

void gcd(int a, int b, int &x0, int &y0, int &d)
{
    if (!b)
    {
        x0 = 1;
        y0 = 0;
        d = a;
    }
    else
    {
        int x, y;
        gcd(b, a % b, x, y, d);

        x0 = y;
        y0 = x - (a / b) * y;
    }
}

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

    int a, b, d, x, y;
    in >> a >> b;

    gcd(a, b, x, y, d);

    while (x < 0) x += b;

    out << x << "\n";

    return 0;
}