#include <iostream>
#include <fstream>

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

int a, n, x, y;

void inversmod (int a, int n, int &x, int &y)
{
	if (n == 0)
	{
		x = 1;
		y = 0;
	}
	else 
	{
		int x0, y0;
		inversmod (n, a%n, x0, y0);
		x = y0;
		y = x0-(a/n)*y0;
	}
}

int main () {
	
	fin >> a >> n;
	inversmod (a, n, x, y);
	
	if (x < 0)
		x += n*(abs(x)/n)+n;
	fout << x << "\n";
}