#include <fstream>
using namespace std;

void euclid(long a,long b,long *d,long *x,long *y)
{
 if (b == 0)
   {
    *d = a;
    *x = 1;
    *y = 0;
   }
  else
   {
    long nx,ny;
    euclid(b,a % b,d,&nx,&ny);
    *x = ny;
    *y = nx - (a / b) * ny;
   }
}


int main(void)
{
 fstream fin("inversmodular.in",ios::in);
 fstream fout("inversmodular.out",ios::out);
 long A,N,D,NX,NY;
 fin >> A >> N;
 euclid(A,N,&D,&NX,&NY);
 fout << NX;
 fin.close();
 fout.close();
 return 0;
}