#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

vector<long long> divs;
vector<long long> pinex_stuff;

long long GetIndex(long long a) {
    long long answer = a;
    for (auto stuff: pinex_stuff) {
        answer -= a / stuff;
    }
    return answer;
}

int main() {
    ifstream cin("frac.in");
    ofstream cout("frac.out");
    long long n, p;
    cin >> n >> p;
    if ((n & 1) == 0) {
        while ((n & 1) == 0) {
            n >>= 1;
        }
        divs.push_back(2);
    }
    for (long long d = 3; d * d <= n; d += 2) {
        if (n % d == 0) {
            while (n % d == 0) {
                n /= d;
            }
            divs.push_back(d);
        }
    }
    if (n > 1) {
        divs.push_back(n);
    }
    for (int i = 1; i < (1 << divs.size()); ++ i) {
        int num = 0;
        long long p = 1;
        for (int j = 0; j < divs.size(); ++ j) {
            if (i & (1 << j)) {
                ++ num;
                p *= divs[j];
            }
        }
        pinex_stuff.push_back(p * ((num & 1) ? 1 : -1));
    }
    long long left = 0, right = (1LL << 61), best = -1;
    while (left <= right) {
        long long middle = (left + right) / 2;
        long long index = GetIndex(middle);
        if (index == p) {
            best = middle;
            right = middle - 1;
        } else if (index < p) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    cout << best << "\n";
    return 0;
}