#include<stdio.h>

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() {
	FILE* fin = fopen("inversmodular.in", "r");
	int a, b;
	fscanf(fin, "%d %d\n", &a, &b);
	fclose(fin);
	
	int d, x, y;
	euclid(a, b, &d, &x, &y);
	x = x % b;
	if(x < 0) {
		x = x + b;
	}
	
	FILE* fout = fopen("inversmodular.out", "w");
	fprintf(fout, "%d\n", x);	
	fclose(fout);
	return 0;
}