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