#include <cstdio>

int a,n,d,x,y;

void euclid ( int a, int b, int &d, int &x, int &y ) {
	if (b == 0) {
		d = a;
		x = 1;
		y = 0;
	} else {
		int x0, y0;
		euclid(b, a % b, d, x0, y0);
		x = y0;
		y = x0 - (a / b) * y0;
	}
}

int main() {
	freopen("inversmodular.in","rt",stdin);
	freopen("inversmodular.out","wt",stdout);
	scanf("%d %d",&a,&n);
	for (euclid(a,n,d,x,y); x < 0; x += n);
	printf("%d\n",x);
	return 0;
}