#include <fstream>

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

int a,n;

pair<int,int> euclidExt(int x,int y)
{
    if(y==0)
        return {1,0};
    pair<int,int> p = euclidExt(y,x%y);
    return {p.second, p.first-(x/y)*p.second};
}

int main()
{
    fin>>a>>n;
    int x=euclidExt(a,n).first;
    while(x<0)
        x+=n;
    fout<<x;
    return 0;
}