#include<stdio.h>

#pragma warning(push)
#pragma warning(disable: 4996)

int A, N;

void gcd(int &x, int &y, int a, int b)
{
	if (!b)
	{
		x = 1;
		y = 0;
	}
	else
	{
		gcd(x, y, b, a % b);
		int aux = x;
		x = y;
		y = aux - y * (a / b);
	}

}

int main()
{
	int inv, ins;

	freopen("inversmodular.in", "r", stdin);
	freopen("inversmodular.out", "w", stdout);

	scanf("%d%d", &A, &N);
	gcd(inv, ins, A, N);

	if (inv < 0)
		inv = N + inv % N;

	printf("%d\n", inv);

	return 0;
}

#pragma warning(pop)