//Invers modular - log(N)

#include <fstream>
#define LL long long
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

LL N,A,X,Y;

LL gcd(LL a,LL b,LL &x,LL &y)
{
     if(!b){x=1,y=0;return a;}
     LL  x0,y0,D;
     D=gcd(b,a % b, x0,y0);
     x=y0;
     y=x0-(a/b)*y0;
     return D;
}


int main()
{
     LL A,N,inv,ins;
     f>>A>>N;
     gcd(A,N,inv,ins);
     while(inv<=0)inv+=N;
     g<<inv<<'\n';
     return 0;
}