#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

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

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