#include <cstdio>

FILE *fin, *fout;

int a, n;

int x, y;

void invmod(int a, int n, int &x, int &y) {
	if (n == 0) {
		x = 1, y = 0;
		return;
	}
	int x1, y1;
	invmod(n, a % n, x1, y1);
	x = y1;
	y = x1 - (a / n) * y1;
}

int main() {
	fin = fopen("inversmodular.in", "r");
	fout = fopen("inversmodular.out", "w");
	fscanf(fin, "%d%d", &a, &n);
	//a * x + n * y = 1
	invmod(a, n, x, y);
	while (x <= 0)
		x += n;
	fprintf(fout, "%d", x);
	fclose(fin);
	fclose(fout);
	return 0;
}