#include <fstream>

using namespace std;

int a, b;

void gcd(long long &x, long long &y, int a, int b)
{
    if(b == 0){
        x = 1;
        y = 0;
    }else{
        gcd(x, y, b, a%b);
        long long aux = x;
        //printf("%d %d\n", x, y);
        x = y;
        y = aux - y * (a/b);
    }
}

int invers_modular(int a, int b)
{
    long long x, y;
    gcd(x, y, a, b);
    if(x < 0)
        x = b + x%b;
    return x;
}

int main()
{
    ifstream fin ("inversmodular.in");
    ofstream fout ("inversmodular.out");
    fin >> a >> b;
    fout << invers_modular(a, b) << "\n";
    return 0;
}