#include <iostream>
#include <fstream>

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

using namespace std;

void extins(int a, int b, int& x, int& y) {
    /// Declare the variable r, that will store the remainder and the variables
    /// z and t, which will keep the solution at the current point.
    int r;
    int z, t;

//    g << a << ' ' << b << "\n";

    if (b != 0) {

        extins(b, a%b, x, y);
    }
    if (b == 0) {
        x = 1;
        y = 0;
    }
    else {
        z = y;
        t = x - (a/b)*y;

        x = z;
        y = t;
    }
}


int main()
{
    /// Cele doua numere pentru care vom rula algoritmul
    int a, b;
    /// Perechea de solutii
    int x, y;
    f >> a >> b;

    extins(a, b, x, y);

//    g << x <<
//     " " << y << "\n";

    if (x < 0) {
        g << x + a << "\n";
    } else {
        g << x << "\n";
    }
    return 0;
}