# include <fstream>
# include <cstring>
# include <algorithm>
# include <vector>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

int a, n, x, y, d;

void euclid( int a, int b, int &d, int &x, int &y ){
	if ( b == 0 ){
		d = a;
		x = 1;
		y = 0;
	}
	else{
		int x0, y0;
		euclid( b, a % b, d, x0, y0 );
		x = y0;
		y = x0 - ( a / b ) * y0;
	}
}


int main(){
	f >> a >> n;
	euclid( a, n, d, x, y );
	//g << x << " " << y << "\n";
	g << x;
	return 0;
}