#include<fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
long long a,n,inv,ins;
inline void modular(long long &x, long long &y, int a, int b)  
{long long aux;
    if (!b)  
	{	x = 1;
		y = 0; 
    }		
	else  
	{   modular(x, y, b, a % b);
		aux = x;
		x = y;
		y = aux - y * (a / b);
	}
}
int main()
{   fin >> a >> n;
    modular(inv, ins, a, n);
    if (inv <= 0)
       inv = n + inv % n;
    fout << n;
    return 0;
}