#include <stdio.h>  
long long a,n,q,r1,r2,r3,u1,u2,u3,v1,v2,v3,x;
void euclid()
{
	while(v3)
	{
		q=u3/v3;
		r1=u1-q*v1;	r2=u2-q*v2;	r3=u3-q*v3;
		u1=v1;u2=v2;u3=v3;
		v1=r1;v2=r2;v3=r3;
	}
	x=u1;
	
	
}
  
int main()  
{  
    freopen("inversmodular.in", "r", stdin);  
    freopen("inversmodular.out", "w", stdout);  
    
    scanf("%lld %lld", &a, &n);  
    u3=a;v3=n;u1=v2=1;u2=v1=0;
	euclid();
	while(x<0) x+=n;
	printf("%lld\n",x);
    return 0;  
}