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

using namespace std;

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

ll a, b, n, x, y;

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

    ll xx = x, yy = x;
    euclid(b, a % b, xx, yy);

    y = xx - (a / b) * yy;
    x = yy;
}

int main() {
    in >> a >> n;

    euclid(a, n, x, y);

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

    return 0;
}