#include <stdio.h>
#define ll long long

int a, n;

void egcd(ll &x, ll &y, int m, int mod) {
    if (!mod) {
        x = 1;
        y = 0;
    } else {
        egcd(x, y, mod, m % mod);
        ll t = x;
        x = y;
        y = t - y * (m / mod);
    }
}

int main() {
    ll inv = 0, tmp;

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

    scanf("%d %d", &a, &n);
    egcd(inv, tmp, a, n);

    if (inv <= 0)
        inv = n + inv % n;

    printf("%lld\n", inv);

    return 0;
}