#include <fstream>

using namespace std;

ifstream f("frac.in");
ofstream g("frac.out");

long long N, P;
long long primes[25];

long long gcd (long long A, long long B) {
	if (B == 0)
		return A;
	return gcd (B, A % B);
}

void go() {
	long long fact = 2;
	long long _N, __N;
	_N = __N = N;
	
	while (fact * fact <= _N && __N > 1) {
		if (__N % fact == 0) {
			primes[++primes[0]] = fact;
			while (__N % fact == 0)
				__N /= fact;
		}
		fact++;
	}
		
	if (__N > 1)
		primes[++primes[0]] = __N;
}

long long pinex (long long X) {
	long long sum = 0;
	
	for (int conf = 1; conf < (1 << primes[0]); conf++) {
		int sgn = 0;
		long long prod = 1;
		for (int i = 0; i < primes[0]; i++)
			if (conf & (1 << i)) {
				sgn++;
				prod *= primes[i + 1];
			}
		if (sgn % 2 == 1)
			sum += X / prod;
		else
			sum -= X / prod;
	}
	
	return X - sum;
}

long long binsearch (long long lo, long long hi) {
	while (lo <= hi) {
		long long mid = lo + (hi - lo) / 2;
		long long howMany = pinex(mid);
		if (howMany < P)
			lo = mid + 1;
		else if (howMany > P)
			hi = mid - 1;
		else if (gcd (mid, N) != 1)
			hi = mid - 1;
		else
			return mid;
	}
}

int main() {
	f >> N >> P;
	go();
	g << binsearch (1LL, (1LL << 61));
	
	return 0;
}