#include <stdio.h>

int euclid_extins(int A, int N, int *X, int *Y) {
    if (N == 0) {
        *X = 1;
        *Y = 0;
        return A;
    }
    int x1, y1;
    int d = euclid_extins(N, A % N, &x1, &y1);
    *X = y1;
    *Y = x1 - (A / N) * y1;
    return d;
}

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

    int A, N;
    fscanf(fin, "%d %d", &A, &N);

    int X, Y;
    euclid_extins(A, N, &X, &Y);

    if (X < 0) X += N;
    fprintf(fout, "%d\n", X);

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