#include <fstream>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

inline void Euclid(int a, int b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
    }
    else {
        long long xx, yy;

        Euclid(b, a % b, xx, yy);
        x = yy;
        y = xx - (a / b) * yy;
    }
}

inline void Read() {
    long long inv, inb;
    int A, N;

    fin >> A >> N;

    Euclid(A, N, inv, inb);

    while (inv < 0)
        inv += N;

    fout << inv;
}

int main () {
    Read();

    fin.close(); fout.close(); return 0;
}