#include<fstream.h>
ifstream f("inversmodular.in"); ofstream g("inversmodular.out");
long long a,b,q,r,n;
long long s,s1,s2,t,t1,t2;
int main()
{f>>a>>n; 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;
  }
 r=s%n; 
 if(s) g<<r<<'\n'; 
  else g<<n-r<<'\n';
 g.close(); return 0;
}