#include <cstdio>

typedef long long ll;

using namespace std;

ll N, P;
bool p[110000];
ll primes[10460], Pr;
int dividePrimes[40], D;

void read() {
	freopen( "frac.in", "r", stdin );
	freopen( "frac.out", "w", stdout );
	scanf("%lld %lld", &N, &P);
}

inline void precomputePrimes() {
	for(int i = 3; i <= 400; i+=2)
		if(!p[i]) {
			for(int j = i * i; j <= 110000; j+=2 * i)
				p[j] = true;
		}

	primes[0] = 2;
	Pr = 1;

	for(int i = 3; i < 110000; i+=2)
		if (!p[i]) {
			primes[Pr] = i;
			Pr++;
		}
}

void inline getDividePrimes(ll B) {
	D = 0;
    int i,d;
    dividePrimes[0]=0;
    for(i=0;i< Pr && primes[i]*primes[i]<=B;++i)
    {
        d=primes[i];
        if(N%d==0)
        {
            dividePrimes[D++]=d;
            while(N%d==0)
                N/=d;
        }
    }
    if(B>1)
        dividePrimes[D++]=N;
}

inline ll compute(long long A)
{
    int i,j,nr,val;
    ll sol=0, prod;
    val=(1<<D);
    sol=A;
    for(i=1;i<val;++i)
    {
        nr=0; prod=1;
        for(j=0;j < D;++j)
            if((1<<j)&i)
            {
                ++nr;
                prod=prod*1LL*dividePrimes[j];
            }
        if(nr%2)
            nr=-1;
        else
            nr=1;
        sol=sol+1LL*nr*A/prod;
    }
    return sol;
}

int main() {
	read();
	precomputePrimes();
	getDividePrimes(N);

	ll l = 1, r = 1l << 61, C = -1, m = 0, sol = -1;
	while( l <= r ) {
		m = l + (r - l) / 2;
		C = compute(m);

		if (C >= P) {
			sol = m;
			r = m - 1;
		}
		else
			l = m + 1;
	}

	printf("%lld\n", sol);
	return 0;
}