#include <bits/stdc++.h>
#define LL long long

using namespace std;

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

void gcd(LL& x, LL& y, LL a, LL b) {
    if (b == 0) {
        x = 1;
        y = 0;
        return;
    }

    gcd(x, y, b, a % b);
    LL aux = x;
    x = y;
    y = aux - a / b * y;
}

int main() {
    LL a, n, inv, y;
    fin >> a >> n;
    gcd(inv, y, a, n);
    while (inv < 0)
        inv += n;
    fout << inv;
    return 0;
}