#include <iostream>
#include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

int InvMod(int a,int b)
{ int i,k,c,x2,y2,x,y,r[35],aux=b;

   while(b)
   { c=a%b; k++; r[k]=a/b;
     a=b; b=c;
   }

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

  while(x<0) x+=aux;

  return x;
}


int main()
{ int a,n;
   f>>a>>n;

   g<<InvMod(a,n);
    return 0;
}