#include <stdio.h>
FILE *f,*g;
int n,a,x,y,x0,y0;
using namespace std;
void euclid (int a,int n)
{int c;
    if (n!=0)
    {

        euclid (n,a%n);

    }
   else
   {
       x=1;
       y=0;
   }
   if (n!=0) {x0=x;
   y0=y;
   x=y0;
   y=x0-(a/n)*y0;}
}
int main()
{f=fopen ("inversmodular.in","r");
 g=fopen ("inversmodular.out","w");
 fscanf (f,"%d%d",&a,&n);
 euclid (a,n);
 while (x<0)
    x+=n;
 fprintf (g,"%d",x);
    return 0;
}