#include <fstream>

using namespace std;

void gcd(int a, int b, int& x, int& y) {

    if (b == 0) {

        x = 1;
        y = 0;
    }
    else {

        gcd(b, a % b, x, y);
        int aux = y;
        y = x - (a / b) * y;
        x = aux;
    }
}

int main()
{
    int A, N, x, y;
    ifstream in("inversmodular.in");
    in >> A >> N;
    in.close();

    gcd(A, N, x, y);

    if (x <= 0)
        x = N + x % N;

    ofstream out("inversmodular.out");
    out << x << "\n";
    out.close();

    return 0;
}