#include <fstream>

using namespace std;

void EuclidExtins(int x, int n, int& y, int& c, int &d)
{
    if(n==0){
        y = 1;
        c = 0;
        d = x;
        return;
    }
    EuclidExtins (n, x%n, y, c, d);
    int y1=c;
    int c1(y-c*(x/n));
    y=y1;
    c=c1;
}

int main()
{
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    int x,n;
    int y,c,d;
    fin>>x>>n;
    EuclidExtins(x,n,y,c,d);
    if(y>=0)
        fout<<y%n;
    else
        fout<<y%n+n;

}