#include <iostream>
#include <fstream>
#include <string>
using namespace std;

typedef long long lol;
ifstream fin("frac.in");
ofstream fout("frac.out");

lol N, P;
lol desc[10];

inline lol check(lol num)
{
	lol ret = 0;
	for (int i = 1; i < (1 << desc[0]); i++)
	{
		lol foo = 1, sign = -1;
		for (int j = 0; j < desc[0]; j++)
			if (i & (1 << j))
				foo = foo * desc[j + 1], sign = -sign;
		ret = ret + (num / foo) * sign;
	}
	return num - ret;
}

inline lol bs(lol P)
{
	lol i = 0, cnt = 1LL << 61;
	for (; cnt > 0; cnt >>= 1)
		if (check(i + cnt) <= P)
			i += cnt;
	return i;
}

int main()
{
	fin >> N >> P;
	int DN = N;
	for (int i = 2; i * i <= N && DN > 1; i++)
	{
		if (DN % i == 0)
			desc[++desc[0]] = i;
		while (DN % i == 0)
			DN /= i;
	}
	if (DN > 1) desc[++desc[0]] = P;
	
	fout << bs(P - 1) + 1 << '\n';
	fout.close();
	return 0;
}