#include <fstream>

using namespace std;

int euclid(int a,int b,int& x,int& y){
	if(b==0){
		x=1,y=0;
		return a;
	}else{
		int x0,y0,d=euclid(b,a%b,x0,y0);
		x=y0;
		y=x0-y0*(a/b);
	}
}
int main(){
	fstream fin("inversmodular.in",ios::in);
	fstream fout("inversmodular.out",ios::out);
	int a,x,n,y;
	fin>>a>>n;
	euclid(a,n,x,y);
	while(x<0){
		x+=n;
	}
	fout<<x;
}