#include <fstream>

int A, N;

using namespace std;

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

void euclid_extins(long long int &x, long long int &y, int a, int b);

int main()
{
    long long int inv = 0, ins;

    fin>>A>>N;

    euclid_extins(inv, ins, A, N);

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

    fout<<inv<<'\n';
    return 0;
}

void euclid_extins(long long int &x, long long int &y, int a, int b)
{
     if(!b)
     {
        x=1; y=0;
        return;
     }

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