#include <stdio.h>

typedef long long ll;

FILE* fin;
FILE* fout;

void Euclid(ll a, ll b, ll* d, ll* x, ll* y)
{
	if (b == 0)
	{
		*d = a;
		*x = 1;
		*y = 0;
	}
	else
	{
		ll x0, y0;
		Euclid(b, a % b, d, &x0, &y0);
		*x = y0;
		*y = (*d - (a * (*x))) / b;
	}
}

int main(void)
{
	ll a, n;
	ll d, x, y;

	fin = fopen("inversmodular.in", "r");
	fout = fopen("inversmodular.out", "w");

	fscanf(fin, "%lld %lld", &a, &n);

	Euclid(a, n, &d, &x, &y);

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

	fprintf(fout, "%lld", x);

	fclose(fin);
	fclose(fout);

	return 0;
}