#include <fstream>

using namespace std;

ifstream cin ("inversmodular.in");
ofstream cout ("inversmodular.out");

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

int main() {

    int a , b;
    cin>>a>>b;
    int x , y;
    euclid_3 (a , b , x , y);
    if (x <= 0){
        x = b + x%b;
    }
    cout<<x;
    //cout<<" "<<y;

    return 0;
}