#include<iostream>
#include<fstream>

using namespace std;

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

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

int main() {
	int a, b;
	fin >> a >> b;

    int d=0, x=0, y=0;

    e(a, b, d, x, y);

    while (x < 0)
        x += b;

    fout << x << endl;

	return 0;
}