#include <fstream>
using namespace std;

long long v[1<<7],a[1<<15],m;

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

long long ired(long long x)
{
	long long i,nr=0; 
	for (i=1;i<=v[0];i++)
		nr+=x/v[i];
	return x-nr;
}

long long bs(long long x)
{
	long long i,step=(long long)1<<40;
	for (i=0;step;step>>=1)
		if (ired(i+step)<x)
			i+=step;
	return i+1;
}

int main()
{
	long long n,i,j,p,k;
	in>>n>>k;
	for (i=2;i*i<=n;i++)
		if (n%i==0)
		{
			for (;n%i==0;n/=i);
			a[++m]=-i;
		}
	if (n!=1)
		a[++m]=-n;
	for (i=1;i<1<<m;i++)
		for (p=i,v[i]=-1,j=1;p;p>>=1,j++)
			if (p&1)
				v[i]*=a[j];
	v[0]=i-1;
	out<<bs(k)<<"\n";
	return 0;
}