// ModularInverse.cpp : Defines the entry point for the console application.
//

#define ll long long


#include "iostream"
#include "fstream"

using namespace std;

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

ifstream input;
ofstream output;

int main()
{
	input.open("inversmodular.in");
	output.open("inversmodular.out");

	int a, n;
	ll x, y;
	input >> a >> n;

	computeInverse(x, y, a, n);

	if (x < 0) x += n;

	output << x;
	

	input.close();
	output.close();
	return 0;
}