#include <cstdio>

#define FIN "inversmodular.in"
#define FOUT "inversmodular.out"
#define LL long long

LL A, N;

	void ecx (LL a, LL n, LL &x, LL &y)
	{
		if (!n)
			x = 1, y = 0;
		else 
		{
			ecx (n, a % n, x, y);
			LL nt = x; x = y, y = nt - y*(a / n);
		}
	}

	int main ()	
	{
		LL x, y;

		freopen (FIN, "r", stdin);
		freopen (FOUT, "w", stdout);

		scanf ("%lld %lld", &A, &N);
		ecx(A, N, x, y);
		
		if (x <= 0) x = N + x%N;
		printf ("%lld\n", x);
		
		return 0;
	}