//#include <iostream>
#include <fstream>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
void invu(int a, int b, int &inv, int & inc) {
    if(!b) {
        inv = 1, inc = 0;
    }
    else {
        invu(b, a % b, inv, inc);
        int aux = inv;
        inv = inc;
        inc = aux - inc * (a / b);
    }
}
int main()
{
    int a, b, inv, inc;
    cin >> a >> b;
    invu(a, b, inv, inc);
    if(inv > 0) cout << inv;
    else cout << (inv + b) % b;
}