#include <bits/stdc++.h>
using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

void inversModular(long long A, long long N, long long& X, long long& Y)
{
	if (!N)
	{
		X = 1;
		Y = 0;
		return;
	}

	long long X0, Y0;
	inversModular(N, A % N, X0, Y0);

	X = Y0;
	Y = X0 - Y0 * (A / N);
}

int main()
{
	long long A, N, X, Y; fin >> A >> N;
	inversModular(A, N, X, Y);

	fout << (X <= 0 ? X % N + N : X);
	return 0;
}