#include <iostream>
#include <fstream>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

long long euclid(long long a, long long b, long long& x, long long& y) {

    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    long long xa, ya;
    int d = euclid(b, a % b, xa, ya);

    x = ya;
    y = xa - (a / b) * ya;

    return d;
}

int main() {

    long long a, b;
    f >> a >> b;

    long long x, y;

    euclid(a, b, x, y);

    x = (x+ b) % b;

    g << x;

    return  0;
}