#include<fstream>
using namespace std;
int a,n;
long long x=1,y,tmp;
void euclid(int a,int b) {
	if(b) {
		euclid(b,a%b);
		tmp=x;
		x=y;
		y=tmp-y*(a/b);
	}
}
int main() {
	int a,n;
	ifstream in("inversmodular.in");
	in>>a>>n;
	in.close();
	euclid(a,n);
	if(x<1) x=n+x%n;
	ofstream out("inversmodular.out");
	out<<x<<'\n';
	out.close();
	return 0;
}