#include <cstdio>
#include <cmath>

using namespace std;

long long n, p [20], P;

int ok (long long x) {
    int v, ns, b, num = 0;
    long long ans, ans2;

    ns = (1 << p [0]);
    ans = x;
    for (v = 1; v < ns; v ++) {
        num = 0;
        ans2 = 1;
        for (b = 0; b < p [0]; b ++)
            if (v & (1 << b)) {
                num ++;
                ans2 = ans2 * p [b + 1];
            }
        ans2 = n / ans2;
        if (num % 2 == 0)
            ans = ans + ans2;
        else ans = ans - ans2;
    }
    if (ans == P)
        return 0;
    if (ans < P)
        return -1;
    return 1;
}

int main () {
    long long lim, d, ex, last, m, st, dr, cn;
    int val;

    freopen ("frac.in", "r", stdin);
    freopen ("frac.out", "w", stdout);

    scanf ("%lld%lld", &n, &P);
    cn = n;
    lim = sqrt (n);
    d = 2;
    ex = 0;
    while (n % 2 == 0) {
        ex ++;
        n = n / 2;
    }
    if (ex) {
        p [++ p [0]] = 2;
    }
    d = 3;
    while (n != 1 && d <= lim) {
        ex = 0;
        while (n % d == 0) {
            n = n / d;
            ex ++;
        }
        if (ex) {
            p [++ p [0]] = d;
        }
        d = d + 2;
    }
    if (n != 1) {
        p [++ p [0]] = n;
    }
    st = 1;
    dr = (1ll << 62) - 1;
    n = cn;
    while (st <= dr) {
        m = (st + dr) / 2;
        val = ok (m);
        if (val == 0) {
            last = m;
            dr = m - 1;
        }
        else
            if (val == 1)
                dr = m - 1;
            else st = m + 1;
    }
    printf ("%lld\n", last);
    return 0;
}