#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 i=0;i<=k;i++)
        v[i] = 0;
    while (!v[0]) {
        long long i = k;
        while (v[i] == 1) {
            v[i] = 0;
            i--;
        }
        v[i] = 1;

        long long prod = 1, nr = 0;
        for (long long i=1;i<=k;i++)
            if (v[i] == 1)
                prod *= D[i], 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;
        }
        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;
}