#include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int euclid(long long int a,long long int b,long long int &x,long long int &y )
{
    if (b == 0)
    {
        x = 1;
        y = 0;
    }
   else{
   long long int x0, y0;
    euclid( b, a % b, x0, y0 );

    x = y0;
    y = x0 - (a / b) * y0;
}
}

int main()
{
   long long int a,b,c,x,y;
       f>>a>>b;
       euclid(a,b,x,y);
       if(x<=0)
        x=b+x%b;
       g<<x;
}