#include <stdio.h>

void gcd(long long& x, long long& y, int a, int b) {
  if (b == 0) {
    x = 1;
    y = 0;
  } else {
    gcd(x, y, b, a % b);
    long long r = x;
    x = y;
    y = r - y * (a / b);
  }
}

int main() {

  freopen("inversmodular.in", "r", stdin);
  freopen("inversmodular.out", "w", stdout);

  int a, n;
  scanf("%d%d", &a, &n);

  long long x = 0, y;
  gcd(x, y, a, n);
  if (x <= 0)
    x = n + x % n;
  printf("%d\n", x);

  return 0;
}