#include<stdio.h>
using namespace std;
FILE *f1=fopen("inversmodular.in","r");
FILE *f2=fopen("inversmodular.out","w");
int a,n,x,y,k;
void euclid(int a,int b,int &x,int &y){
   int x0,y0,h;
   if (b==0){
      x=1;
      y=0;
      return;
   }
     else{
        euclid(b,a%b,x,y);
        h=a/b;
        x0=x;
        y0=y;
        x=y0;y=x0-h*y0;
     }
}
int main(){
   fscanf(f1,"%d%d",&a,&n);
   fclose(f1);
   euclid(a,n,x,y);
   if (x>=n) x=x%n;
     else
       if (x<0){
          k=1;
          x=x+k*n;
          while(x<0){
            k++;
            x=x+k*n;
          }
       }
   fprintf(f2,"%d",x);
   fclose(f2);
   return 0;
}