#include<fstream>
using namespace std;
long  a,b,d,x,y,z,n,i;
void euclid(long a,long b,long z,long &x,long &y)
{
	long  x0,y0;
	if (b==0){
		z=a;
		x=1;
		y=0;
	}
	else {
		euclid(b,a%b,z,x0,y0);
		x=y0;
		y = x0 - (a / b) * y0;
	}
}
		
int main(){
	ifstream f("inversmodular.in");
	ofstream g("inversmodular.out");
	f>>a>>n;
	euclid(a,n,1,x,y);
	while (x<0)
		x=x+n;
	g<<x;
	return 0;
}