#include <cstring>
#include <cstdio>
#include <cmath>

long long a, b;

long long megold(long long a, long long b) {
	long long ax = 1, bx = 0, cx, d, r;
	while (b) {
		d = a / b;
		r = a % b;

		cx = bx;
		bx = ax - d * bx;
		ax = cx;

		a = b;
		b = r;
	}
	return(ax);
}

int main() {
	FILE * in = fopen("inversmodular.in", "rt");
	FILE * out = fopen("inversmodular.out", "wt");

	fscanf(in, "%lld%lld", &a, &b);
	long long x = megold(a, b);
	if (x > 0) {
		fprintf(out, "%lld", x);
	} else {
		fprintf(out, "%lld", b + x % b);
	}
	fclose(in);
	fclose(out);
}