#include <fstream>
using namespace std;

ifstream fi ("inversmodular.in");
ofstream fo ("inversmodular.out");
int n, m;

void invmd(long long *x, long long *y, int a, int b)
{
	if (b == 0)
	{
		*x = 1;
		*y = 0;
	}
	else
	{
		long long x0, y0;
		invmd(&x0, &y0, b, a%b);
		*x = y0;
		*y = x0 - (a/b)*y0;
	}
}

int invers(int a, int b)
{
	long long rez, aux;
	invmd(&rez, &aux, a, b);
	if (rez < 0)
		rez = b + rez%b;
	return rez;
}

int main()
{
	fi >> m >> n;
	fo << invers(m, n);
	return 0;
}