#include <cstdio>
#include <vector>
using namespace std;
#define pb push_back
vector<long long > prim;
long long p;
void pre(long long x)
{
	for (long long i=2;i*i<=x;i++)
	{
		//printf("i=%lld %d\n",i,!(x%i));
		if (!(x%i))
			prim.pb(i);
		while (!(x%i))
			x/=i;		
	}	
	if (x!=1)
		prim.pb(x);
}
long long val(long long x,long long y)
{
	long long val2=-1;
	for (long long i=1,t=0;t<=prim.size()-1;i<<=1,t++)
		if (x&i)
		{
			val2*=prim[t]*(-1);
		}
	return y/val2;
}
bool ver(long long x)
{
	long long  nr=0,n=(1<<prim.size())-1,i;
//	printf("%lld\n",n);
	for (i=1;i<=n;i++)
	{
	//	printf("AAAA\n");
		//printf("%lld %lld %lld\n",i,x,val(i,x));
		nr+=val(i,x);
	}
	if (x-nr>=p)
		return 1;
	return 0;
}
int main()
{
	FILE *in ,*out;
	long long n,i,rez;
	in=fopen("frac.in","r");
	out=fopen("frac.out","w");
	fscanf(in,"%lld%lld",&n,&p);
	//printf("%lld\n",n);
	pre(n);
	rez=0;
	for (i=((long long )1)<<60;i;i>>=1)
	{
		rez+=i;
		//printf("%lld %d\n",rez,ver(rez));
		if (ver(rez))
			rez-=i;
	}
	rez+=1;
	fprintf(out,"%lld\n",rez);
	fclose(in);
	fclose(out);
	return 0;	
}