#pragma warning (disable:4996)

#include <stdio.h>

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


int main()
{
	int A, x, y, N; 

	FILE *f, *g;

	f = fopen("inversmodular.in", "rt");
	g = fopen("inversmodular.out", "wt");

	fscanf(f, "%d", &A);
	fscanf(f, "%d", &N);

	euclid_extins(&x, &y, A, N);

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

	fprintf(g, "%d", x);

	fclose(f);
	fclose(g);
	return 0;
}