#include <fstream>

using namespace std;
ifstream cin ("inversmodular.in");
ofstream cout ("inversmodular.out");

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

int main()
{
	long long x , n;
	cin >> x >> n;
	long long X , Y;
	Euclid(x , n , X , Y);
	while(x < 0)
        x += n;
	cout << X;
}