#include<fstream>

using namespace std;


long long a,b;
int x,y;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

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

int main(){
	
	f>>a>>b;
	euclid(a,b,x,y);
	
	if(x<=0)
		x=b+x%b;
	
	g<<x;
	
	return 0;
}