#include <cstdio>

using namespace std;

#define FIN "inversmodular.in"
#define FOUT "inversmodular.out"

long long modular_inverse(long long a, long long n) {
  long long x0 = 1, y0 = 0, x1 = 0, y1 = 1, bufn = n;

  while (n) {
    long long q = a / n;
    long long r = a % n;
    long long x = x0 - q * x1;
    long long y = y0 - q * y1;
    a = n;
    n = r;
    x0 = x1;
    x1 = x;
    y0 = y1;
    y1 = y;
  }

  if (x0 < 0) {
    long long cnt = -(x0 / bufn);
    x0 += bufn * (cnt + 1);
    x0 %= bufn;
  }

  return x0;
}

int main(void) {
  freopen(FIN, "r", stdin);
  freopen(FOUT, "w", stdout);

  long long a, n;

  scanf("%lld%lld", &a, &n);
  printf("%lld\n", modular_inverse(a, n));

  return 0;
}