#include <fstream>
#define mF "inversmodular"
std::ifstream in(mF ".in");
std::ofstream out(mF ".out");
#include <tuple>
int x, y, d; void f(int a, int b)
{
    if (b) f(b, a % b), std::tie(x, y) = std::make_tuple(y, x - (a/b)*y);
    else std::tie(d, x, y) = std::make_tuple(a, 1, 0);
}
int main() {int e, m; in >> e >> m; f(e, m); out << (x < 0? m + x % m: x);}