#include <stdio.h>

long long x,y,a,b,d;

void euclid(long long a,long long b,long long * cmmdc,long long * x,long long * y)
// a*x+b*y=cmmdc a>b
{
   if (b==0)
   {
   	*cmmdc=a;
   	*x=1;
   	*y=0; 
   	return ;
   }

   long long tmp1,tmp2;
   euclid(b,a%b,cmmdc,&tmp1,&tmp2);

   //b*tmp1+(a-(a/b)*b)*tmp2=a*x+b*y
   //b*(tmp1-(a/b)*tmp2-y)=a*(x-tmp2)
   *y=(tmp1-(a/b)*tmp2);
   *x=tmp2;
}


int main(int argc, char const *argv[])
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
    
     scanf("%lld%lld",&a,&b);

     euclid(a,b,&d,&x,&y);
    

     if (x<0)
     	x=x+b;
     printf("%lld",x);
	return 0;
}