#include<stdio.h>

long long n,p,d[32],nr;

void fact(long long n) {
	long long i;
	for(i=2;i*i<=n;++i) {
		if(n%i==0) {
			d[nr++]=i;
			while(n%i==0)
				n/=i;
		}
	}
	if(n!=1)
		d[nr++] = i;
}

long long f(long long q) {
	long long r=0,par,p,i,j;
	for(i=0;i<(1<<nr);++i) {
		par=1; p=1;
		for(j=0;j<nr;++j)
			if((i&(1<<j))!=0) {
				p*=d[j];
				par*=-1;
			}
		r+=q/(par*p);
	}
	return r;
}

int main() {
	long long i,pas=(long long)1<<60;
	freopen("frac.in","r",stdin);
	freopen("frac.out","w",stdout);
	scanf("%lld%lld",&n,&p);
	fact(n);
	for(i=0;pas!=0;pas>>=1) {
		if(f(i+pas)<p)
			i+=pas;
	}
	printf("%lld",i+1);
	return 0;
}