#include<cstdio>
#include<cmath>

#include<vector>
using std::vector;

long long n,p;

vector<int> v;
int m;

long long calc (long long x)
{
	long long ret=x;
	for(int c=1;c<(1<<m);c++){
		long long y=1;
		for(int i=0;i<m;i++)
			if((1<<i)&c)
				y*=-v[i];

		ret+=x/y;
	}

	return ret;
}

int main (void)
{
	freopen ("frac.in","r",stdin);
#ifdef INFOARENA
	freopen ("frac.out","w",stdout);
#endif

	scanf ("%lld%lld",&n,&p);
	if(p==1){
		puts ("1");
		return 0;
	}

	int lim=sqrt (n);
	for(int i=2;i<=lim;i++)
		if(n%i==0){
			while(n%i==0)
				n/=i;
			v.push_back (i);
			lim=sqrt (n);
		}
	if(n)
		v.push_back (n);
	m=v.size();

	long long s=1, e=1LL<<61;

	while(s<=e){
		long long m=(s+e)/2;
		long long mr=calc (m);
		if(mr<p)
			s=m+1;
		else if(mr>p)
			e=m-1;
		else{
			while(calc (m-1)==p)
				m--;
			printf ("%lld",m);
			return 0;
		}
	}

	return 42;
}