#include <bits/stdc++.h>

using namespace std;

#define CIURMAX 110000
#define ll long long

bool isPrime[CIURMAX];
vector<int> primes;
ll N;

ll gcd(ll A, ll B)
{
    ll r;
    while (B != 0) {
        r = A % B;
        A = B;
        B = r;
    }

    return A;
}

void ciur()
{
    memset(isPrime, true, sizeof(isPrime));

    primes.push_back(2);

    for (int i = 3; i < CIURMAX; i+= 2) {
        if (!isPrime[i])
            continue;
        primes.push_back(i);
        for (int j = i + i; j < CIURMAX; j += i)
            isPrime[j] = 0;
    }
}

ll solve(ll A)
{
    ll B = N;
    vector<int> p;

    for (int i = 0; i < primes.size() && primes[i] * primes[i] < B; i++) {
        if (!(B % primes[i]))
            p.push_back(primes[i]);

        while (!(B % primes[i]))
            B /= primes[i];
    }

    if (B > 1)
        p.push_back(B);

    int n = p.size();

    ll sol = 0;
    for (int conf = 1; conf < (1 << n); conf++ ) {
        ll prod = 1;
        int k = 0;
        for (int i = 0; i < n; i++)
            if (conf & (1 << i))
                prod *= p[i], k++;

        if (k % 2)
            sol += A / prod;
        else
            sol -= A / prod;
    }

    return A - sol;
}

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

    ciur();

    ll P;

    f >> N >> P;

    ll l, r;
    l = 0;
    r = (1LL<<61) + 1;

    ll ans = 0;

    while (l < r) {
        ll mid = (l+r)/2;

        ll sol = solve(mid);
        if ( sol < P)
            l = mid+1;
        else if (sol > P)
            r = mid-1;
        else {
            if (gcd(mid, N) == 1) {
                ans = mid;
                l = r + 1;
            } else {
                r = mid;
            }
        }
    }

    g << ans << endl;
}