#include <stdio.h>
#include <stdint.h>

void read_int32_t(FILE *__restrict stream, int32_t *__restrict nr) {
    uint8_t ch;
    *nr = 0;
    while ((ch = fgetc(stream)) && ('0' <= ch && ch <= '9')) {
        *nr *= 10;
        *nr += ch - '0';
    }
    if (ch == '\r') {
        fgetc(stream);
    }
}

void aee(int32_t a, int32_t b, int32_t *x, int32_t *y, int32_t *d) {
    if (b == 0) {
        *d = a;
        *x = 1;
        *y = 0;
        return;
    }
    int32_t xx, yy, q = a / b;
    aee(b, a % b, &xx, &yy, d);
    *x = yy;
    *y = xx - q * yy;
}

int main() {
    int32_t x, y, d;
    int32_t a, n;
    {
        FILE *__restrict in = fopen("inversmodular.in", "r");
        read_int32_t(in, &a);
        read_int32_t(in, &n);
        fclose(in);
    }

    aee(a, n, &x, &y, &d);

    {
        FILE *__restrict out = fopen("inversmodular.out", "w");

        fprintf(stdout, "%lli\n", (long long) ((long long) n + (long long) x % n) % n);

        fclose(out);
    }
    return 0;
}