#include <iostream>
#include <fstream>
#include <tuple>

std::tuple<int, int, int> gcd(int a, int b) {
    int x0(1), x1(0), y0(0), y1(1);
    int aux, div;

    while (b) {
        div = a / b;
        aux = b;
        b = a % b;
        a = aux;

        aux = x1;
        x1 = x0 - div * x1;
        x0 = aux;

        aux = y1;
        y1 = y0 - div * y1;
        y0 = y1;
    }

    return std::make_tuple(a, x0, y0);
}

int main() {
    std::ifstream fileIn("inversmodular.in");
    std::ofstream fileOut("inversmodular.out");

    int a, b;

    fileIn >> a >> b;

    int x(std::get<1>(gcd(a, b)));

    while (x < 0) {
        x += b;
    }

    fileOut << x;

    fileIn.close();
    fileOut.close();
    return 0;
}