#include<fstream>
#include<iostream>
using namespace std;

typedef long long int64;
int64 EuclidExt(int64 a, int64 b, int64 &x, int64 &y)
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	else
	{
		int64 xi,yi;
		int64 cmmdc=EuclidExt(b, a%b, xi, yi);
		x=yi;
		y=xi-(a/b)*x;
		return cmmdc;
	}
}

int main()
{
	fstream fin("inversmodular.in",fstream::in);
	fstream fout("inversmodular.out",fstream::out);
	int64 a,n,x,y;
	fin>>a>>n;
	fin.close();
	EuclidExt(a,n,x,y);
	if(x<0)
		x+=((x/n+1)*n);
	fout<<x<<"\n";
	fout.close();
	return 0;
}