#include <fstream>
using namespace std;
fstream fin, fout;

void euclid(int a, int b, int& x, int &y)
{
   if (b == 0)
      x = y = 1;
   else
   {
      int x1, y1;
      euclid(b, a%b, x1, y1);
      x = y1;
      y = x1 - a/b*y1;
   }
}

int main()
{
   fin.open("inversmodular.in", std::ios::in);
   fout.open("inversmodular.out", std::ios::out);

   int a, n, x, y;
   fin >> a >> n;
   
   euclid(a, n, x, y);

   while (x < 0)
      x += n;

   fout << x;

   fin.close();
   fout.close();
   return 0;
}