#include <iostream>
#include <fstream>

using namespace std;

void euclid(int a, int b, int &x, int &y)
{
    if (b==0)
    {
        x=1;
        y=0;
        return;
    }
    euclid(b, a%b, x, y);
    if (x || y)
    {
        int aux=y;
        y=x-(a/b)*y;
        x=aux;
    }
}

int main()
{
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    int a, b, x, y;
    fin >> a >> b;
    euclid(a, b, x, y);
    while(x<0)
        x+=b;
    fout << x;
    return 0;
}