#include <fstream>

using namespace std;

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

long long n, a, x, y;

long long cmmdc(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    } else {
        long long xa, ya;
        long long r = cmmdc(b, a%b, xa, ya);
        x = ya;
        y = xa - ya*(a/b);
        return r;
    }
}

int main() {
    fin>>a>>n;
    cmmdc(a, n, x, y);

    fout<<(x%n+n)%n;

}