#include <stdio.h>

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

int main (void) {
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);
	
	int a, n, x, y;
	
	scanf("%d %d", &a, &n);
	
	euclid (n, a, &x, &y);
	
	while (x < 0) x+=n;
	
	printf("%d", x);
	
	
	return 0;
}