#include <fstream>
using namespace std;

int invmod(int a, int n)
{
    int r0 = a, x0 = 1, y0 = 0;
    int r1 = n, x1 = 0, y1 = 1;

    while (r1 != 1) {
        int q2, r2, x2, y2;

        q2 = r0 / r1;
        r2 = r0 % r1; // r0 - q2*r1

        x2 = x0 - q2*x1;
        y2 = y0 - q2*y1;

        r0 = r1; x0 = x1; y0 = y1;
        r1 = r2; x1 = x2; y1 = y2;
    }

    if (x1 < 0) {
        int q = (-x1) / n;
        x1 += q * n;
        if (x1 < 0)
            x1 += n;
    }

    return x1;
}


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

    int a, n;
    fin >> a >> n;

    fout << invmod(a, n);


    return 0;
}