#include <fstream>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

int a, n, x1, y1;

void cmmdc(int a, int b, int &x, int &y)
{
    if (b == 0)
        x = 1, y = 0;
    else
    {
        int xx = 0, yy = 0;
        cmmdc(b, a%b, xx, yy);
        x = yy;
        y = xx-(a/b)*yy;
    }
}

int main()
{
    f >> a >> n;
    cmmdc(a, n, x1, y1);
    if (x1 <= 0)
        x1 = n+x1%n;
    g << x1;
    return 0;
}