#include <fstream>
using namespace std;

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

int x, y, a, b;

void Invers (int a, int b, int &x, int &y);

int main()
{
    fin >> a >> b;

    Invers(a, b, x, y);

    if (x <= 0)
        x = b + x % b;

    fout << x;
}

void Invers(int a, int b, int &x, int &y)
{
    if ( b == 0 )
    {
        x = 1;
        y = 0;
        return;
    }

    int x0, y0, t = a / b;

    Invers( b, a - b * t, x0, y0);

    x = y0;
    y = x0 - t * y0;
}