#include <iostream>
using namespace std;

void gcd(long long& x, long long& y, int a, int b) {
    if (b == 0) {
        x = 1;
        y = 0;
    } else {
        gcd(x, y, b, a % b);
        long long aux = x;
        x = y;
        y = aux - y * (a / b);
    }
}

int main() {
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);

    int a, n;
    cin >> a >> n;

    long long x = 0, y;
    gcd(x, y, a, n);

    if (x <= 0) {
        x = x + n;
    }

    cout << x;
}