#include<fstream>
#include<cmath>
using namespace std;
int rad,prime[300001],pr,D;
long long st,dr,m,prod[300001],n,d,p,divizori[300001];
bool neprim[1000006];
long long verifica(long long x)
{
	long long sol=x;
	for(int i=1;i<(1<<D);i++)
	sol+=x/prod[i];
	return sol;
}
void ciur()
{
	for(int i=2;i<=rad;i++)
	if(!neprim[i])
	{
		prime[++pr]=i;
		for(int j=i+i;j<=rad;j+=i) neprim[i]=j;
	}
}
int main()
{
	int i,j,nr;
	long long x;
	long long sol;
	ifstream fi("frac.in");
	ofstream fo("frac.out");
	fi>>n>>p;
	rad=(int)sqrt((double)n);
	ciur();
	x=n;
	for(d=1;d<=pr and prime[d]<=rad;d++)
	{
		if(n%prime[d]) continue;
		while(x%prime[d]==0) x/=prime[d];
		divizori[++D]=prime[d];		
	}
	if(x!=1) divizori[++D]=x;
	for(i=1;i<(1<<D);i++)
	{
		prod[i]=1;
		nr=0;
		for(j=0;j<D;j++)
		if(i&(1<<j)) {nr++; prod[i]*=divizori[j+1]; }
		if(nr%2) prod[i]=-prod[i];
	}
	st=1;
	dr=(1LL<<61);
	while(st<dr)
	{
		m=(st+dr)/2;
		sol=verifica(m);
		if(sol>=p) dr=m-1; else if(sol<p) st=m+1; 
		//else if(sol==p) st=dr=m;
	}
	fo<<st<<"\n";
	return 0;
}