#include <stdio.h>

void euclid(long long *x, long long *y, int a, int b) {
    if (b == 0) {
        *x = 1;
        *y = 0;
    } else {
        long long x_prim, y_prim;
        euclid(&x_prim, &y_prim, b, a % b);
        *x = y_prim;
        *y = x_prim - y_prim * (a / b);
    }
}

int main() {
    int A, N;
    FILE *fin = fopen("inversmodular.in", "r");
    FILE *fout = fopen("inversmodular.out", "w");
    long long inv = 0, ins = 0;
    fscanf(fin, "%d %d", &A, &N);

    euclid(&inv, &ins, A, N);

    if (inv < 0) {
        inv += N;
    }

    fprintf(fout, "%lld", inv);
    
    fclose(fin);
    fclose(fout);
    
    return 0;
}