#include <stdio.h>

void extgcd(long long a, long long b, long long *x, long long *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return;
    }
    long long x1, y1;
    extgcd(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
}

int main() {
    FILE *fin = fopen("inversmodular.in", "r");
    FILE *fout = fopen("inversmodular.out", "w");
    long long a, n, x, y;

    if (fscanf(fin, "%lld %lld", &a, &n) == 2) {
        extgcd(a, n, &x, &y);
        x = (x % n + n) % n;
        fprintf(fout, "%lld\n", x);
    }

    fclose(fin);
    fclose(fout);
    return 0;
}