#include <stdio.h>

// Euclid extins: gaseste x, y cu a*x + b*y = gcd(a, b)
long long euclid_extins(long long a, long long b, long long *x, long long *y) {
    if (b == 0) {
        *x = 1; *y = 0;
        return a;
    }
    long long x1, y1;
    long long g = euclid_extins(b, a % b, &x1, &y1);
    *x = y1;                        // transformare coeficienti
    *y = x1 - (a / b) * y1;
    return g;
}

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

    long long A, N;
    fscanf(fin, "%lld %lld", &A, &N);

    // A*x + N*y = 1  rezulta   A*x ≡ 1 (mod N)  rezulta  x este inversul modular
    long long x, y;
    euclid_extins(A, N, &x, &y);

    x = ((x % N) + N) % N;         // normalizare: x poate fi negativ

    fprintf(fout, "%lld\n", x);

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