#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 x1 = 0, y1 = 0;
  euclid_extins(b, a % b, x1, y1);
  x = y1;
  y = x1 - y1 * (a / b);
}

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