#include <fstream>

using namespace std;
ifstream cin ("");
ofstream cout ("");

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

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