#include<fstream>
std::ifstream fin("inversmodular.in");
std::ofstream fout("inversmodular.out");
int a, n;
void invers(int &k, int &l, int a, int b)
{
    if(!b)
    {
        k=1;
        l=0;
        return;
    }
    int kp, lp;
    invers(kp, lp, b, a%b);
    k=lp;
    l=kp-lp*(a/b);
}
int main()
{
    fin>>a>>n;
    int k, l;
    invers(k, l, a, n);
    while(k<0)
        k+=n;
    fout<<k<<'\n';
    return 0;
}