#include <fstream>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
void euclid(int A, int B, int &X, int &Y)
{
    if(B==0)
    {
        X=1;
        Y=0;
        return;
    }
    int X0, Y0;
    euclid(B, A%B, X0, Y0);
    X=Y0;
    Y=X0-(A/B)*Y0;
}
int main()
{
    int A, B;
    fin>>A>>B;
    int X, Y;
    euclid(A, B, X, Y);
    if(X<=0)
        X=B+X%B;
    fout<<X;
    return 0;
}