#include <fstream>
#define int long long

void euclid_extins(int a, int b, int &x, int &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return;
  }
  int xx = x, yy = y;
  euclid_extins(b, a % b, xx, yy);
  x = yy;
  y = xx - yy * (a / b);
}

signed main() {
  std::ifstream fin("inversmodular.in");
  std::ofstream fout("inversmodular.out");
  int a, n;
  fin >> a >> n;
  int x, y;
  euclid_extins(a, n, x, y);
  fout << (x + n) % n;
  return 0;
}