#include <fstream>
#include <vector>

using namespace std;

ifstream f("frac.in");
ofstream g("frac.out");

long long N, P, rez, st = 1, dr = (1LL << 61), mij;
vector<long long> divi;

void factPrimi()
{
	for(long long d = 2; d * d <= N; ++d)
		if(N % d == 0)
		{
			divi.push_back(d);
			do
			{
				N /= d;
			}
			while(N % d == 0);
		}
	if(N > 1)
		divi.push_back(N);
}

long long pinex(long long A)
{
	long long lim = (1 << divi.size()), k, mc, D = A;
	for(int i = 1; i < lim; ++i)
	{
		k = 0, mc = 1;
		for(int j = 0; (1 << j) <= i; ++j)
			if(i & (1 << j))
			{
				k++;
				mc *= divi[j];
			}
		if(k % 2 == 0) D += A / mc;
		else D -= A / mc;
	}
	return D;
}

int main()
{
	f >> N >> P;
	factPrimi();
	while(st <= dr)
	{
		mij = (st + dr) / 2;
		if(P <= pinex(mij))
			rez = mij, dr = mij - 1;
		else
			st = mij + 1;
	}
	g << rez;
	f.close();
	g.close();
	return 0;
}