/*
aflarea celui mai mic numar natural x
a.i. k*x%n=1
*/#include <fstream>
#define In "inversmodular.in"
#define Out "inversmodular.out"
using namespace std;

void Euclid_extins(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x = 1;
        y = 0;
        return;
    }
    int q=a/b,aux;
    Euclid_extins(b,a%b,x,y);
    aux = x;
    x = y;
    y = aux - y*q;
}

int main()
{
    int n,k,inv,x;
    ifstream fin(In);
    fin>>k>>n;
    fin.close();
    Euclid_extins(k,n,inv,x);
    ofstream fout(Out);
    fout<<inv<<"\n";
    fout.close();
    return 0;
}