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