#include <stdio.h>

int x, y;
void gcd(int a, int b) {
    if (!b) {
        x = 1;
        y = 0;
    } else {
        gcd(b, a % b);
        int aux = x;
        x = y;
        y = aux - y * (a / b);
    }
}
int main (void) {
    FILE *f;
    int a, n;

    f = fopen("inversmodular.in", "r");
    fscanf(f, "%d%d", &a, &n);
    fclose(f);

    gcd(a, n);
    if (x <= 0)
       x = n + x % n;

    f = fopen("inversmodular.out", "w");
    fprintf(f, "%d\n", x);
    fclose(f);
    return 0;
}