#include <stdio.h>

typedef long long ll;

ll N, A;

ll euclid_ext(ll a, ll b, ll &x, ll &y) {
   if (b == 0) {
      x = 1;
      y = 0;
      return a;
   }
   ll x0, y0, d;
   d = euclid_ext(b, a % b, x0, y0);
   x = y0;
   y = x0 - (a / b) * y0;
   return d;
}

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

   scanf("%lld %lld", &A, &N);

   ll inv, dummy;
   euclid_ext(A, N, inv, dummy);

   if (inv <= 0) {
      inv = N +  inv % N;
   }
   printf("%lld", inv);

   fclose(stdin);
   fclose(stdout);
   return 0;
}