#include <cstdio>
void cmmdc(int a,int b,int *x,int *y){
     if(b==0){
        *x=1;
        *y=0;
     }
     else{
         int x0,y0;
         cmmdc(b,a%b,&x0,&y0);
         *x=y0;
         *y=x0-(a/b)*y0;
     }
}
int main(){
   FILE*fi,*fout;
   int a,n,x,y;
   fi=fopen("inversmodular.in" ,"r");
   fout=fopen("inversmodular.out" ,"w");
   fscanf(fi,"%d%d" ,&a,&n);
   cmmdc(a,n,&x,&y);
   while(x<0)
     x+=n;
   fprintf(fout,"%d" ,x);
   fclose(fi);
   fclose(fout);
   return 0;
}