//Ilie Dumitru
#include<cstdio>

long long int divPrm[50], cntD;
long long int prodMask[1<<20], parit[1<<20];

void factorizare(long long int N)
{
	long long int i;

	if(N%2==0)
	{
		while(N%2==0)
			N>>=1;
		divPrm[0]=2;
		cntD=1;
	}

	for(i=3;i*i<=N;i+=2)
	{
		if(N%i==0)
		{
			while(N%i==0)
				N/=i;
		}
		divPrm[cntD++]=i;
	}

	if(N>1)
		divPrm[cntD++]=N;
}

void genMasks(int k=0, int mask=0, int par=0, long long int prod=1)
{
	if(k==cntD)
	{
		prodMask[mask]=prod;
		parit[mask]=par;
	}
	else
	{
		genMasks(k+1, mask, par, prod);
		genMasks(k+1, mask|(1<<k), par^1, prod*divPrm[k]);
	}
}

long long int cntCoPrime(long long int K)
{
	int mask;
	long long int ans=K;

	for(mask=1;mask<(1<<cntD);++mask)
	{
		if(parit[mask])
			ans-=K/prodMask[mask];
		else
			ans+=K/prodMask[mask];
	}

	return ans;
}

int main()
{
	FILE* f=fopen("frac.in", "r"), *g=fopen("frac.out", "w");
	//FILE* f=stdin, *g=stdout;
	long long int N, P, l, r, mid;

	fscanf(f, "%lld%lld", &N, &P);
	factorizare(N);
	genMasks();

	l=0;
	r=1LL<<61;
	while(r-l>1)
	{
		mid=l+((r-l)>>1);
		if(cntCoPrime(mid)<P)
			l=mid;
		else
			r=mid;
	}

	fprintf(g, "%lld\n", r);

	fclose(f);
	fclose(g);
	return 0;
}