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