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

//#include "stdafx.h"
#include <fstream>

using namespace std;

int inversmodular(long long a, long long n)
{
	int x = 1, x2 = 0;
	int y = 0, y2 = 1;
	long long aux = n;
	while (n != 0)
	{
		int c = a / n;
		int r = a % n;
		a = n;
		n = r;
		int xnou, ynou;
		xnou = x - c * x2;
		ynou = y - c * y2;
		x = x2;
		y = y2;
		x2 = xnou;
		y2 = ynou;
	}
	if (x <= 0) x = aux + x % aux;
	return x;
}

int main()
{
	ifstream fin("inversmodular.in");
	ofstream fout("inversmodular.out");
	long long a, n;
	fin >> a >> n;
	fout << inversmodular(a, n) << '\n'; 
	return 0;
}