#include <fstream>

using namespace std;

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

int A, N;

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

int main()
{
    long long int invers=0, aux;

    fin>>A>>N;

    euclid_extins(invers, aux, A, N);

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

    fout<<invers<<'\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);
}