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