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

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

void euclid(int A, int N, int& X, int& Y)
{
	if (!N)
	{
		X = 1;
		Y = 0;
		return;
	}
	euclid(N, A % N, X, Y);
	int CX = X;

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

int main()
{
	int A, N, X, Y; 

	fin >> A >> N;
	euclid(A, N, X, Y);

	if (X <= 0) X = N + X % N;
	fout << X;
}