/*
    Complexitate O(log n)
*/
#include<fstream>

using namespace std;

int a, n, x, y;

void Euclid(int a, int n, int &x, int &y)
{
    if(n == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    int x0 = 0, y0 = 0;
    Euclid(n, a % n, x0, y0);
    x = y0;
    y = x0 - y0 * (a / n);
}

int main()
{
    ifstream fin("inversmodular.in");
    fin >> a >> n;
    fin.close();

    Euclid(a, n, x, y);
    if(x < 0)
        x = n + x % n;

    ofstream fout("inversmodular.out");
    fout << x << "\n";
    fout.close();
    return 0;
}