#include <fstream>

using namespace std;

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

    int D, X0, Y0;
    D = gcd (B, A%B, X0, Y0);
    X = Y0;
    Y = X0 - (A / B) * Y0;

    return D;
}

bool ExtendedEuclid (int A, int B, int &X, int &Y, int D) {
    int C = gcd (A, B, X, Y);
    if (D % C) {
        X*= D / C;
        Y*= D / C;
        return 1;
    }
    return 0;
}

int invertMod (int a, int n) {
    int x, y;
    ExtendedEuclid(a, n, x, y, 1);

    while (x < 0)
        x+=n;

    return x;
}

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

    int a, n;
    fin >> a >> n;
    int i = invertMod (a, n);

    fout << i;

    return 0;
}