#include <iostream>
#include <fstream>

using namespace std;

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


int calculInversModular(int a, int n, int &x, int &y) {
    if (n == 0) {
        x = 1;
        y = 0;
        return a;
    }

    int x_val, y_val;
    int gcd_val = calculInversModular(n, a % n, x_val, y_val);

    x = y_val;
    y = x_val - (a / n) * y_val;

    return gcd_val;
}

int main() {


    int n_val, a_val;
    fin >> a_val >> n_val;

    int x_val, y_val;
    int gcd_val = calculInversModular(a_val, n_val, x_val, y_val);

    if (x_val < 0) {
        while (x_val < 0)
            x_val += n_val;
    }

    fout << x_val;

    return 0;
}