#include <fstream>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
void f(long long int & x, long long int& y, int a, int b);
int a, b;
long long int x, y;
int main()
{x=0;
 fin>>a>>b;
 f(x, y, a, b);
 if(x<=0)
    x=b+x%b;
 fout<<x;
 return 0;
}
void f(long long int & x, long long int& y, int a, int b)
{long long int aux;
 if (b==0)
     {x=1; y=0;}
     else
     {f(x, y, b, a % b);
      aux=x;
      x=y;
      y=aux-y*(a/b);
     }

}