#include <fstream>
using namespace std;

int N, A, X, Y;
void citire();
void euclid (int a, int b, int &x, int &y);
void afisare();

int main()
{
    citire();
    euclid (A, N, X, Y);
    if (X<0) X=N+N%X;
    afisare();
    return 0;
}

void citire()
{
    ifstream fin ("inversmodular.in");
    fin>>A>>N;
    fin.close();
    return;
}

void afisare()
{
    ofstream fout ("inversmodular.out");
    fout<<X<<"\n";
    fout.close();
    return;
}

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

    int x0, y0;
    euclid (b, a%b, x0, y0);

    x=y0;
    y=x0-a/b*y0;
}