#include <cstdio>
#include <cstdlib>
#pragma warning(disable: 4996)
using namespace std;

int euclid(int a, int b, int &x, int &y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	else
	{
		int cmmdc = euclid(b, a%b, x, y), xx;
		xx = x;
		x = y;
		y = xx - (a / b) * y;
		return cmmdc;
	}
}

int main()
{
	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);
	int a, b, cmmdc;
	int x, y;

	scanf("%d %d %d", &a, &b);

	cmmdc = euclid(a, b, x, y);
	if (cmmdc != 1)
	{
		printf("eroare\n");
		exit(EXIT_FAILURE);
	}

	if (x <= 0)
	{
		x = x%b + b;
	}

	printf("%d\n", x);
	return 0;
}