#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

void euclidExtins(int a, int b, int& d, int& x, int& y)
{
	if (!b)
	{
		x = 1;
		y = 0;
		d = a;
	}
	else
	{
		euclidExtins(b, a % b, d, x, y);
		int x0 = x;
		int y0 = y;
		x = y0;
		y = x0 - (a / b) * y0;
	}
}
int main()
{
	FILE* fin = fopen("inversmodular.in", "r");
	FILE* fout = fopen("inversmodular.out", "w");

	int  a, b, d=0;
	fscanf(fin, "%d%d", &a, &b);
	int x = 0, y = 0;
	euclidExtins(a, b, d, x, y);
	fprintf(fout, "%d",x);
}