#include <cstdio>
int a, n;

int gcdExtended(int a, int b, long long& x, long long& y) {
  if (!b) {
    x = 1; y = 0;
    return a;
  }
  
  long long x1, y1;
  int d = gcdExtended(b, a % b, x1, y1);
  x = y1;
  y = -a / b * y1 + x1;
  return d;
}

int main() {
  freopen("inversmodular.in", "r", stdin);
  freopen("inversmodular.out", "w", stdout);
  
  scanf("%d%d", &a, &n);
  
  long long x, y;
  gcdExtended(a, n, x, y);
  
  x %= n;
  if (x < 0) x += n;
  printf("%lld\n", x);
  return 0;
}