#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long i64;

vector<i64> divs;

void getDivs(i64 N) {
    for (int i = 2; 1LL * i * i <= N; ++i) {
        if (N % i == 0) {
            divs.push_back(i);
            while (N % i == 0)
                N /= i;
        }
    }

    if (N > 1)
        divs.push_back(N);
}

i64 getAns(i64 P) {
    if (P == 0)
        return 0;

    i64 ans = 0;

    int N = divs.size();
    for (int conf = 0; conf < (1 << N); ++conf) {
        i64 prod = 1;
        int sign = 1;

        for (int i = 0; i < N; ++i) {
            if (conf & (1 << i)) {
                prod *= divs[i];
                sign *= -1;
            }
        }

        ans += P / prod * sign;
    }

    return ans;
}

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

    i64 N, P;
    scanf("%lld%lld", &N, &P);

    getDivs(N);
    i64 cycle = getAns(N);
    i64 newP = P % cycle;

    i64 ans = N;
    for (i64 step = (1LL << 33); step; step >>= 1) {
        if (ans - step >= 0 && getAns(ans - step) >= newP)
            ans -= step;
    }

    ans = N * (P / cycle) + ans;

    printf("%lld\n", ans);
}