#include <iostream>
#include <fstream>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
int a, b, d, t, x, y;
void f(int a, int b, int &d, int &x, int &y)
{
    if(b == 0)
        d = a, x = 1, y = 0;
    else
    {
        int nr1, nr2;
        f(b, a % b, d, nr1, nr2);
        x = nr2, y = nr1 - (a / b) * nr2;
    }
}
int main()
{
    in >> a >> b;
    f(a, b, d, x, y);
    if(x < 0)
        x = x + (x / b + 1) * b;
    out << x;
    return 0;
}