using namespace std;

#include <cstdio>
#include <algorithm>

#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define IN "frac.in"
#define OUT "frac.out"
#define II inline 
#define ll long long
#define VAL_MAX 1LL<<61

ll N,P;
ll bit;
ll stv[30];

ll number(ll x);
void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	scanf("%lld%lld",&N,&P);
}

void desc()
{
	FOR(i,1,29)
		stv[i] = 1;
	ll n = N;
	if((n >> 1LL) << 1LL == n)
		stv[ ++stv[0] ] = 2; 
	for(;(n >> 1LL) << 1LL == n;n >>= 1LL);
	for(ll i=3;i*i<=n;i+=2)
	{	
		if(N / i * i == n)
			stv[ ++stv[0] ] = i;
		for(;n / i * i == n;n /= i); 
	}	
	if(n > 1) stv[++stv[0]] = n;
}

ll find()
{
	ll m,Step;
	for(Step = 1;Step < VAL_MAX;Step <<= 1LL);
	for(m=1;Step;Step >>= 1LL)
  		if(m + Step <= VAL_MAX &&  number(m+Step-1) < P)
			m += Step;
	return m;	
}


void biti(ll i,ll &prod,ll &cate)
{  
	prod = bit = 1;  
    cate=0;  
    for(;i && bit <= stv[0] ;++bit,i >>= 1LL)
	{
		if(i & 1)
		{  
            ++cate;  
            prod *= stv[bit];  
        }
	}	
}

 
ll number(ll x)
{
	ll s(x),prod;  
    ll cate; 
	
    for(ll i=1;i < (1LL<<stv[0]);++i)
	{  
        biti(i,prod,cate);  
        if(cate & 1)  
            s -= x / prod;  
        else 
			s += x / prod;  
    }  
    return s;  
}	

int main()
{
	scan();
	desc();
	printf("%lld\n", find() );
	return 0;
}