#include<stdio.h> 
#include<math.h>

struct fact
{long long f;int s;};


fact f[100000];
int fac[10000];
bool ciur[110000];


int main()
{
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	long long n,p,v,k,i,j,lim,ns,dr,st,med;
	scanf("%lld%lld",&n,&p);
	if(n==1)
	{
		printf("%lld\n",p);
		return 0;
	}
	lim=sqrt(n);
	for(i=2;i<=lim;++i)
		if(!ciur[i])
		{
			if(n%i==0)
				fac[++fac[0]]=i;
			for(j=i+i;j<=n;j=j+i)
				ciur[j]=1;
		}
	if(!ciur[n])
		fac[++fac[0]]=n;
	k=fac[0];
	ns=(1<<k)-1;
	for(v=1;v<=ns;++v)
	{
		lim=0;
		f[++f[0].f].f=1;
		for(j=0;j<k;++j)
			if(v&(1<<j))
			{
				++lim;
				f[f[0].f].f=f[f[0].f].f*fac[k-j];
			}
		if(lim%2==1)
			f[f[0].f].s=1;
		else
			f[f[0].f].s=-1;
	}
	dr=1<<61;
	st=1;
	k=f[0].f;
	while(st<=dr)
	{
		med=(dr+st)>>1;
		lim=0;
		for(i=1;i<=k;++i)
			if(f[i].s==1)
				lim=lim+med/f[i].f;
			else
				lim=lim-med/f[i].f;
		if(med-lim==p)
			break;
		else
			if(med-lim>p)
				dr=med-1;
			else
				st=med+1;
	}
	printf("%lld\n",med);
	return 0;
}