#include <fstream>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

typedef long long tip;

tip a, n;

void euclidExtins(tip a, tip b, tip *x, tip *y){

    if(b == 0){
        *x = 1;
        *y = 0;
    }
    else{
        tip lastX, lastY;
        euclidExtins(b, a % b, &lastX, &lastY);

        *x = lastY;
        *y = lastX - (a / b) * lastY;
    }
}

int main()
{
    f>>a>>n;

    tip x, y;

    euclidExtins(a, n, &x, &y);

    if(x < 0){
        while(x < 0){
            x += n;
        }
    }

    g<<x<<'\n';
    return 0;
}