#include <fstream>

using namespace std;

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

int n, a, x, y, aux;

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

int main() {
    fin >> a >> n;
    cmmdc(n, a, x, y);
    if(y<0) {
        aux = y / n - 1;
        aux = - aux;
        y = (y + n * aux) % n;
    }
    fout << y << "\n";
    return 0;
}