#include<fstream>
using namespace std;
ifstream f("inversmodular.in"); ofstream g("inversmodular.out");
long long a,b,q,r,ai,n,k;
long long s,s1,s2,t,t1,t2;
int main()
{f>>ai>>n; a=ai; b=n;
 s1=1; t1=0;
 s2=0; t2=1;
 r=a%b; q=a/b;
 while(r)
  {s=s1-s2*q; s1=s2; s2=s;
   t=t1-t2*q; t1=t2; t2=t;
   a=b; b=r; r=a%b; q=a/b;
  }
 if(s>0) g<<s<<'\n';
  else
	{k=(-s)/n; r=(-s)%n;
	 if(r) k++;
     g<<s+k*n<<'\n';
	}
 g.close(); return 0;
}