#include<fstream>
using namespace std;
ifstream fi("frac.in");
ofstream fo("frac.out");
long long A[25],n,i,st,dr,mij,rez,x,nd,cn;

long long f(long long x)
{
	long long l=1<<nd,rez=x,prod,i,j;
	for(i=1; i<l; i++)
	{
		prod=1;
		for(j=0; j<nd; j++)
		{
			if(i&(1<<j))
				prod*=-A[j+1];
		}
		rez+=x/prod;
	}
	return rez;
}

int main()
{
	fi>>n>>x;
	cn=n;
	for(i=2; i*i<=n; i++)
	{
		if(n%i==0)
		{
			A[++nd]=i;
			while(n%i==0)
				n/=i;
		}
	}	
	if(n!=1)
		A[++nd]=n;
	n=cn;
	st=1;
	dr=1LL<<61;
	while(st<=dr)
	{
		mij=(st+dr)>>1;
		if(f(mij)<x)
		{
			st=mij+1;
		}
		else
		{
			rez=mij;
			dr=mij-1;
		}
	}
	fo<<rez<<"\n";
	fi.close();
	fo.close();
	return 0;
}