#include <cstdio>

void euclid(int a, int b, int *x0, int *y0) {
  int x, y;
  if(b == 0) {
    x = 1;
    y = 0;
  } else {
    euclid(b, a % b, x0, y0);
    x = *y0;
    y = *x0 - a / b * (*y0);
  }
  *x0 = x;
  *y0 = y;
}

int main() {
  int n, a, x, y;
  FILE *fin = fopen("inversmodular.in", "r");
  fscanf(fin, "%d%d", &a, &n);
  fclose(fin);

  euclid(a, n, &x, &y);

  x = x % n;
  if(x < 0)
    x = x + n;

  FILE *fout = fopen("inversmodular.out", "w");
  fprintf(fout, "%d", x);
  fclose(fout);
  return 0;
}