#include <fstream>
using namespace std;

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

int main()
{
	ifstream fin("inversmodular.in");
	int A,N,val,inv;
	fin>>A>>N;
	fin.close();
	euclid(inv,val,A,N);
	if (inv<=0) inv+=N;
	ofstream fout("inversmodular.out");
	fout<<inv<<"\n";
	fout.close();
	return 0;
}