#include <fstream>
#include <vector>

using namespace std;

ifstream cin("frac.in");
ofstream cout("frac.out");

vector<unsigned long long> prime_divisors;

long long no_name_with_no_understanding(unsigned long long number) {
	long long nicht_versteht_returner = number;
	for (unsigned long long i = 1; i < (1ll << prime_divisors.size()); i++) {
		unsigned long long digits_of_one = 0, i_bak = i;
		unsigned long long nicht_versteht_product = 1;

		for (unsigned long long j = 0; j < prime_divisors.size(); j++) {
			if (i_bak % 2) {
				digits_of_one++;
				nicht_versteht_product *= prime_divisors[j];
			}
			i_bak /= 2;
		}
		nicht_versteht_returner += (digits_of_one % 2 ? -1 : 1) * (number / nicht_versteht_product);
	}
	return nicht_versteht_returner;
}

int main() {
	unsigned long long denominator, required_numerator;
	cin >> denominator >> required_numerator;

	unsigned long long factor = 2, denominator_bak = denominator;
	while (factor * factor <= denominator_bak) {
		if (!(denominator_bak % factor)) {
			prime_divisors.emplace_back(factor);
			do
				denominator_bak /= factor;
			while (!(denominator_bak % factor));
		}
		factor == 2 ? factor = 3 : factor += 2;
	}
	if (denominator_bak != 1)
		prime_divisors.emplace_back(denominator_bak);

	unsigned last_mid = 0;
	unsigned long long lhs = 0, rhs = 1ll << 61;
	while (lhs < rhs) {
		unsigned long long mid = (lhs + rhs) / 2;
		if (no_name_with_no_understanding(mid) >= required_numerator)
			rhs = mid - 1, last_mid = mid;
		else
			lhs = mid + 1;
	}
	cout << last_mid;
}