#include <iostream>
#include <fstream>

using namespace std;

long long N, P, ans;
long long d[20];
int nd;

void Read()
{
    ifstream f ("frac.in");
    f >> N >> P;
    f.close();
}

inline void UpdateX(long long & x, int amount, int semn)
{
    /// nu asa
}

inline long long Count(long long x)
{
    long long ret = x;
    int limit = (1 << nd) - 1;
    for (int conf = 1; conf <= limit; ++ conf)
    {
        int cnt = 0;
        long long prod = 1LL;
        for (int k = 0; k < nd; ++ k)
            if (conf & (1 << k))
            {
                ++ cnt;
                prod = prod * d[k + 1];
            }
        if (cnt & 1)
            ret = ret - (x / prod);
        else
            ret = ret + (x / prod);
    }
    return ret;
}

void Solve()
{
    if (N == 1)
    {
        ans = P;
        return ;
    }
    if (N % 2 == 0)
    {
        d[++nd] = 2;
        while (N % 2 == 0)
            N /= 2;
    }
    for (int i = 3; 1LL * i * i <= N; i += 2)
    {
        if (N % i == 0)
        {
            d[++nd] = i;
            while (N % i == 0)
                N /= i;
        }
    }
    if (N != 1)
    {
        d[++nd] = N;
    }

    long long st = 1, dr = (1LL << 61);
    while (st <= dr)
    {
        long long mij = (st + dr) / 2LL;
        long long now = Count(mij);
        if (now == P)
        {
            ans = mij;
            dr = mij - 1;
        }
        else
            if (now < P)
                st = mij + 1;
            else
                dr = mij - 1;
    }
}

void Write()
{
    ofstream g("frac.out");
    g << ans << "\n";
    g.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}