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