#include <fstream> // reimplementare pentru lab ASD
#include <algorithm>
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
int divprim[31], nrdiv = -1;
long long N, P, d, aux, mask, Max;
long long check (long long x) {
    long long Last = 1 << (nrdiv + 1);
    long long sol = 0;
    for (int i = 1; i < Last ; i++) {
        int cnt = -1;
        long long prod = 1;
        for (int j = 0 ; j <= nrdiv; j++) {
            if (i & (1LL << j) ) {
                prod = prod * divprim[j];
                cnt *= -1;
            }
        }
        sol = sol + cnt * x / prod;
    }
    return x - sol;
}
long long cautbin (long long P) {
    long long sol = 0;
    while (mask) {
        long long test = sol + mask;
        if (test <= Max) {
            long long val = check(test);
            if (val < P) sol = test;
        }
        mask >>= 1;
    }
    return sol + 1;
}
int main() {
    f >> N >> P;
    aux = N;
    if (N % 2 == 0) {
        while (N % 2 == 0)
            N /= 2;
        divprim[++nrdiv] = 2;
    }
    d = 3;
    while(d * d <= N) {
        if (N % d == 0) {
            while (N % d == 0)
                N /= d;
            divprim[++nrdiv] = d;
        }
        d += 2;
    }
    if (N != 1)
        divprim[++nrdiv] = N;
    N = aux;
    mask = 1LL << 61;
    Max = 1LL << 61;
    g << cautbin(P);
    return 0;
}