#include <stdio.h>
long long cmmdc(long long a, long long b, long long *x, long long *y) {
  if (b == 0) {
    *x = 1;
    *y = 0;
    return a;
  }

  long long x1, y1;
  long long c = cmmdc(b, a % b, &x1, &y1);

  *x = y1;
  *y = x1 - (a / b) * y1;
  return c;
}

long long invmod(long long a, long long n) {
  long long x, y;
  long long c = cmmdc(a, n, &x, &y);
  if (c != 1)
    return -1;

  long long inv = (x % n + n) % n;
  return inv;
}

int main(void) {
  long long a, n;
  FILE *in = fopen("inversmodular.in", "r");
  FILE *out = fopen("inversmodular.out", "w");
  if (fscanf(in, "%lld %lld", &a, &n) != 2)
    return 1;

  long long inv = invmod(a, n);
  if (inv == -1)
    fprintf(out, "inversul nu exista");
  else
    fprintf(out, "%lld\n", inv);
  return 0;
}