#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);
     }
}