#include <fstream>

using namespace std;

typedef long long ll;

ll A,N;

void GCD(ll A,ll B,ll &X,ll &Y)
{
    if (B == 0)
    {
        X = 1;
        Y = 0;
        return;
    }

    ll X1,Y1;

    GCD(B,A % B,X1,Y1);
    X = Y1;
    Y = X1 - (A / B) * Y1;
}

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

     fin >> A >> N;

     ll X,Y;

     GCD(A,N,X,Y);

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

     fout << X;

    return 0;
}