#include <bits/stdc++.h>

using namespace std;

void gcd_ext(long long a, long long b, long long &x, long long &y) {
    if (!b) {
        x = 1;
        y = 0;
    } else {
        long long x0, y0;
        gcd_ext(b, a % b, x0, y0);
        x = y0;
        y = x0 - y0 * (a / b);
    }
}

int main() {
    freopen("carici.in", "r", stdin);

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

    long long a, n;
    scanf("%lli%lli", &a, &n);
    long long inv = 0, ins = 0;

    gcd_ext(a, n, inv, ins);

    while (inv <= 0) {
        inv = n + inv % n;
    }
    cout << inv << "\n";

    return 0;
}