#include <fstream>

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

int euc (int a,int b,int &x,int &y)
{
    if(b==0)
    { x=1; y=0;
        return a;
    }
    else
    {int x0,y0,d;
      d=euc(b,a%b,x0,y0);
        x=y0; y=x0-(a/b)*y0;
    }

}
int main()
{
   int a,n;
   fin>>a>>n;
   int x,y;
   euc(a,n,x,y);
   if(x<=0)
    x=n+x%n;
   fout<<x;

    return 0;
}