#include <fstream>

using namespace std;

long long D[100], v[100];
long long n, st, dr, k, p;

long long rez(long long m) {
    long long sol = 0;

    for (long long x = 1; x < (1<<k); x++){
        long long prod = 1, nr = 0;
        for (long long i=0;i<k;i++)
            if ((x >> i) & 1)
                prod *= D[i+1], nr++;
        if (prod != 1)
            if (nr % 2)
                sol += m/prod;
            else
                sol -= m/prod;
    }


    if (sol > 0)
        m -= sol;
    else
        m += sol;

    if (m >= p)
        return 1;
    else
        return 0;

}

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

    fin>>n>>p;
    long long d = 2;
    while (d*d <= n && n!=1) {
        long long e = 0;
        while (n%d == 0) {
            e++;
            n /= d;
        }
        if (e != 0) {
            D[++k] = d;
        }
    }
    if (n!=1) {
        D[++k] = n;
    }

    long long st = 1; dr = (1LL<<61);
    while (st <= dr) {

        long long mid = (st + dr)/2;
        if (rez(mid))
            dr = mid-1;
        else
            st = mid+1;
    }

    fout<<st;

    return 0;
}