#include<fstream>
#define IN "inversmodular.in"
#define OUT "inversmodular.out"
using namespace std;

ifstream fin(IN);
ofstream fout(OUT);

void euclid(long long a,long long b,long long &x,long long &y)
{
     if(b==0){ x=1; y=0; return;}

     long long x0,y0;
     euclid(b,a%b,x0,y0);
     x=y0;
     y=x0-(a/b)*y0;
}


int main()
{
     long long a,n,x,y;
     fin>>a>>n;
     euclid(a,n,x,y);
     while(x<=0)
        x+=n;
     fout<<x<<'\n';

     return 0;
}