#include <cstdio>
#include <algorithm>

using namespace std;

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

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

   return 0;
}