#include <fstream>
#include <vector>

#include <cstring>
using namespace std;

const int MAX_VAL = 110000;

vector < int > primes;
long long N, P, K, ans;
long long a[35];
bool isPrime[MAX_VAL];

void Eratosthenes() {
    memset(isPrime, 1, sizeof(isPrime));

    isPrime[0] = isPrime[1] = 0;
    primes.push_back(2);
    for(int i = 4; i < MAX_VAL; i += 2)
        isPrime[i] = 0;
    for(int i = 3; i < MAX_VAL; i += 2)
        if(isPrime[i]) {
            primes.push_back(i);
            for(int j = i + i; j < MAX_VAL; j += i)
                isPrime[j] = 0;
        }
}

inline long long gcd(long long a, long long b) {
    while(b) {
        long long r = a % b;
        a = b;
        b = r;
    }

    return a;
}

long long solve(long long n) {
    long long ret = 0;

    for(int conf = 1; conf < (1 << K); ++conf) {
        int cnt = 0;
        long long p = 1;

        for(int i = 0; i < K; ++i)
            if(conf & (1 << i)) {
                ++cnt;
                p *= a[i + 1];
            }

        if(cnt % 2)
            ret += n / p;
        else ret -= n / p;
    }

    ret = n - ret;

    return ret;
}

int main() {
    ifstream f("frac.in");
    ofstream g("frac.out");

    f >> N >> P;

    Eratosthenes();

    long long temp = N;
    for(int i = 0; i < (int) primes.size() && 1LL * primes[i] * primes[i] <= temp; ++i)
        if(temp % primes[i] == 0) {
            a[++K] = primes[i];
            while(temp % primes[i] == 0)
                temp /= primes[i];
        }
    if(temp > 1)
        a[++K] = temp;

    for(long long l = 1, m, r = (1LL << 62); l <= r; ) {
        m = (l + r) / 2;

        long long now = solve(m);

        if(now < P)
            l = m + 1;
        else if(now > P)
            r = m - 1;
        else if(now == P) {
            if(gcd(m, N) == 1) {
                ans = m;
                l = r + 1;
            }
            else r = m - 1;
        }
    }

    g << ans << "\n";

    f.close();
    g.close();

    return 0;
}