#include<stdio.h>
using namespace std;
long long v[20],n,p,max;
long long verif(long long a){
	long long x=a,aux,j,k,nr,i;
	for(i=1;i<max;++i){
		aux=1;
		nr=0;
		j=i;
		for(k=1;j;++k,j/=2){
			if(j&1){
				aux*=v[k];
				++nr;
			}
		}
		if(nr&1)
			x-=a/aux;
		else
			x+=a/aux;
	}
	return x;
}
void bin(){
	long long st=1,dr=(long long)1<<60,m;
	while(st!=dr){
		m=(st+dr)/2;
		if(p<=verif(m))
			dr=m;
		else
			st=m+1;
	}
	printf("%lld\n",st);
}
int main () {
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	long long nc;
	scanf("%lld%lld",&n,&p);
	nc=n;
	for(long long i=2;i*i<=nc;++i){
		if(!(nc%i))
			v[++v[0]]=i;
		while(!(nc%i))
			nc/=i;
	}
	if(nc!=1)
		v[++v[0]]=nc;
	for(int i=v[0]+1;i<20;++i)
		v[i]=1;
	max=1<<v[0];
	bin();
	return 0;
}