#include <fstream>

using namespace std;

ifstream fin("frac.in");
ofstream fout("frac.out");

const int DIM = 101;
const int MAX_EXP = 61;

long long n, p;
long long v[DIM], cnt;
bool f[DIM];

bool solve(long long val) {
    memset(f, 0, sizeof(f));
    long long sol = 0;
    while (f[0] == 0) {
        long long index = cnt;
        while (f[index] == 1) {
            f[index] = 0;
            index--;
        }
        f[index] = 1;

        long long prod = 1, num = 0;
        for (int i = 1; i <= cnt; i++) {
            if (f[i] == 1) {
                prod *= v[i];
                num++;
            }
        }

        if (prod != 1) {
            if (num % 2 == 0)   sol -= val / prod;
            else                sol += val / prod;
        }
    }

    if (sol > 0)    val -= sol;
    else            val += sol;
    return val < p;
}

int main() {
    fin >> n >> p;
    for (long long d = 2; n != 1 && d <= n / d; d++) {
        if (n % d == 0) {
            v[++cnt] = d;
            while (n % d == 0)
                n /= d;
        }
    }
    if (n != 1)
        v[++cnt] = n;

    long long left = 1, right = (1LL << MAX_EXP);
    while (left <= right) {
        long long middle = (left + right) / 2;
        if (solve(middle))
            left = middle + 1;
        else
            right = middle - 1;
    }

    fout << left;

    return 0;
}