#include <fstream>
using namespace std;

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

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

    int y;
    x = eec(b, a % b, y);
    return y - x * (a / b);
}

int main()
{
    int a, n, x, y, val;

    fin >> a >> n;

    y = eec(n, a, x);
    if (y < 0) y += n;

    fout << y;
}