#include <iostream>
#include <fstream>
#include <cmath>

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

int eucl_ext(int a, int n, long long& x, long long& y)
{
	if (n == 0)
	{
		x = 1;
		y = 0;
	}
	else
	{
		eucl_ext(n, a % n, x, y);
		long long temp = y;
		y = x - y * (a / n);
		x = temp;
	}
	return (x >= 0) ? x : n + x % n;
}

int main()
{
	int a, n;
	long long x, y;
	fin >> a >> n;
	fout << eucl_ext(a, n, x, y);
}