#include <iostream>

int extendedGCD(int A, int N, int &X, int &Y) {
    if (A == 0) {
        X = 0;
        Y = 1;
        return N;
    }

    int X1, Y1;
    int gcd = extendedGCD(N % A, A, X1, Y1);

    X = Y1 - (N / A) * X1;
    Y = X1;

    return gcd;
}

int findModularInverse(int A, int N) {
    int X, Y;
    int gcd = extendedGCD(A, N, X, Y);
   // std::cout<<(long long)A*X%N;
    if (gcd != 1) {
        // A și N nu sunt prime între ele
        return -1;
    } else {
        // Asigură că inversul modular este pozitiv și între 1 și N-1
        return ((long long)X % N + N) % N;
    }
}

int main() {
  freopen("inversmodular.in", "rt", stdin);
    freopen("inversmodular.out", "wt", stdout);

    int A, N;
    std::cin >> A >> N;

    int inverse = findModularInverse(A, N);

    if (inverse != -1) {
        std::cout << inverse << "\n";
    } else {
        std::cout << "Nu exista invers modular pentru A si N.\n";
    }

    return 0;
}