#include <iostream>
#include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
 int r[50],k;
int Inv(int a,int b)
{ int i,c,x=1,y=0,x2,y2,initb=b;
  while(b)
  { c=a%b; k++; r[k]=a/b;
    a=b; b=c;
  }

  for(i=k;i>=1;i--)
  { x2=y;
    y2=x-y*r[i];
    x=x2; y=y2;
  }
   if (x<0) x+=initb;

 return x;
}

int main()
{ int a,n;
   f>>a>>n;
   g<<Inv(a,n);
 return 0;
}