#include <fstream>

using namespace std;

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

long long int invers(long long int b,long long int n)
{
   long long int cmm,y,x;
   euclid(n,b,&cmm,&x,&y);
   long long int invers=y;
   
   while(y<0)
     y+=n;
   
   return y;
}

int main()
{
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    long long int a,n;
    fin>>a>>n;
    fout<<invers(a,n)<<'\n';
    fin.close();
    fout.close();
    //system("PAUSE");
    return 0;
}