#include <fstream>

using namespace std;

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

void IM(int a, int b, int &d, int &x, int &y)
{
    if (b == 0)
        {
         d = a;
         x = 1;
         y = 0;
        }
    else
        {
         int x0, y0;
         IM (b, a % b, d, x0, y0);
         x = y0;
         y= x0 - (a / b) * y0;
        }
}

int main()
{
    int a, n, d, x, y;
    fin >> a >> n;
    IM (a, n, d, x, y);
    if (x < 0) x = x + n;
    fout << x << "\n";
    fin.close();
    fout.close();
    return 0;
}