#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("inversmodular.in") ;
ofstream fout ("inversmodular.out") ;

long long A , N ;

void Citire ()
{
    fin >> A >> N ;
}

long long InvMod () // A*X - B*N = 1 mod N  ,,, aflu X ;
{
   long long x_0 = 1 , y_0 = 0 , x_1 = 0 , y_1 = 1 , rest , cat , x_r , y_r ;

   while ( A != 0 )
   {
       rest = N % A ;
       cat = N / A ;
       N = A ;
       A = rest ;
       x_r = x_0 - cat * x_1 ;
       y_r = y_0 - cat * y_1 ;
       x_0 = x_1 ;
       y_0 = y_1 ;
       x_1 = x_r ;
       y_1 = y_r ;
   }

   // while ( x_0 < 0 )
         // x_0 += N ;

   while ( y_0 < 0 )
          y_0 += N ;

   return y_0 ;

}

int main()
{
    Citire () ;
    fout << InvMod () ;
    return 0;
}