#include<cstdio>

long long n,nn,k,p;

long long d[20];


long long functie (long long x)
{
	long long i,c,pr,j,nr,s=0;
	for (i=1;i<(1<<d[0]);++i)
	{
		for (c=i,pr=1,j=1,nr=0;c!=0;j++,c>>=1)
			if (c&1)
			{
				pr*=d[j];
				++nr;
			}
		if (nr&1)
			s+=x/pr;
		else 
			s-=x/pr;
	}
	return x-s;
}


long long cautare (long long valoare)
{
	long long i, pas=(long long)(1)<<61;
	
	
	for (i=0;pas!=0;pas>>=1)
		if ( functie (i+pas) <= valoare ) i+=pas; 
	return i+1;
}

int main()
{
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	
	scanf("%lld%lld", &n , &p);
	
	nn=n;
	
	for (long long i=2;i*i<=n;i++)
	{
		if (nn%i==0)
		{
			d[++d[0]]=i;
			while (nn%i==0)	nn/=i;
		}
	}
	
	if (nn!=1) d[++d[0]]=nn;
	
	
	printf("%lld" , cautare(p-1));
	

	return 0;
}