#include <fstream>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int t,a,b,c,x,y,d;
void Euclid(int a,int b,int &d,int &x,int &y)
{ if(b==0) {d=a;x=1;y=0;}
    else {int x0,y0;
         Euclid(b,a%b,d,x0,y0);
         x=y0;
         y=x0-(a/b)*y0;
         }
}
int A,N;
int main()
{ fin>>A>>N;int i;


   d=0;x=0;y=0;
   Euclid(A,N,d,x,y);
   //if(c%d==0) {x=x*(c/d);y=y*(c/d);fout<<x<<" "<<y<<"\n";}
   //else fout<<0<<" "<<0<<"\n";
  if(x<0) x=x+N;fout<<x;


    return 0;
}