#include <iostream>
#include <fstream>

using namespace std;

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

void euclidExt(int a, int b, int &d, int &x, int &y) {
    if (b == 0) {
        d = a;
        x = 1;
        y = 0;
        return;
    }
    int q = a/b, x2, y2;
    euclidExt(b, a - q*b, d, x2, y2);
    x = y2;
    y = x2 - q*y2;
}


int main() {
    int a, n;
    fin >> a >> n;
    int x, y, d = 1;
    euclidExt(a, n, d, x, y);
    fout << (x%n + n)%n << '\n';

    return 0;
}