#include <cstdio>
using namespace std;
long x,y,n,a;
void euclid(long a, long b)
{
	if(b==0){
		x=1;y=0;return;
			}
	long c=a/b;
	euclid(b,a%b);
	long aux=y;y=x-c*aux;x=aux;
}
int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%ld%ld",&a,&n);
	euclid(a,n);
	while(x<0){x+=n;}
	printf("%ld",x);
return 0;
}