#include <fstream>

using namespace std;

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

int x;

void euclid3(int a, int b, int x1, int y1, int x2, int y2)
{
    if(!b) {
        x = x1;
    } else {
        euclid3(b, a % b, x2, y2, x1 - a / b * x2, y1 - a / b * y2);
    }
}
int main()
{
    int a, b;

    fin >> a >> b;

    euclid3(a, b, 1, 0, 0, 1);

    while(x <= 0)
        x += b;

    fout << x;

    return 0;
}