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

void read_uint32_t(FILE *__restrict stream, uint32_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(uint32_t a, uint32_t b, uint32_t *x, uint32_t *y, uint32_t *d) {
    if (b == 0) {
        *d = a;
        *x = 1;
        *y = 0;
        return;
    }
    uint32_t xx, yy, q = a / b;
    aee(b, a % b, &xx, &yy, d);
    *x = yy;
    *y = xx - q * yy;
}

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

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

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

        fprintf(out, "%u\n", (n+ x % n)%n);

        fclose(out);
    }
    return 0;
}