#include <fstream>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
void euclid_extins(long long a, long long n, long long &x, long long &y){
    if (n == 0){
        x = 1;
        y = 0;
        return;
    }
    euclid_extins(n, a % n, x, y);
    long long x2, y2;
    x2 = y;
    y2 = x - (a / n) * y;
    x = x2, y = y2;
}
int main(){
    long long a, n, x = 1, y = 0;
    cin >> a >> n;
    euclid_extins(a, n, x, y);
    while (x < 0) {
        x += n;
    }
    cout << x;
    return 0;
}