#include <fstream>

using namespace std;

int a,n,y,x;

ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");

void cmmdc (int a, int b, int &x, int &y ) {
	
	int xa, ya;
	
	if (b==0) {
		x=1;
		y=0;
		return;
	}else {
		cmmdc (b, a%b, xa, ya);
		x=ya;
		y=xa-(a/b)*ya;
	}
}

int main () {
	
	fin>>a>>n;
	
	cmmdc (n,a,x,y);
	
	if (y<0) 
		y=(y+n*((0-y)/n+1))%n;
	
	fout<<y<<"\n";
	
	
	return 0;
}