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