#include <fstream>
using namespace std;
#define IN "inversmodular.in"
#define OUT "inversmodular.out"

ifstream fin(IN);
ofstream fout(OUT);

void euclid(int&, int&, int, int);

int main(){
    int x, y, a, b;
    fin >>a>>b;
    euclid(x, y, a, b);
    while (x<0)
        x+=b;
    fout <<x<<'\n';
    fout.close();
    return 0;
}

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