#include <bits/stdc++.h>
#define Vmax 110000
#define Dmax 102

using namespace std;
int p[Vmax / 9], d[Dmax];
bool w[Vmax];
long long N, P, Sol;
void read()
{
    freopen("frac.in", "r", stdin);
    freopen("frac.out", "w", stdout);
    scanf("%lld %lld", &N, &P);
}
void sieve()
{
    int i, j;
    bool ok = 0;
    for(i = 2; i < Vmax; ++ i)
        if(!w[i])
        {
            p[++ p[0]] = i;
            if(i * i > Vmax)
                ok = 1;
            if(!ok)
                for(j = i * i; j < Vmax; j += i)
                    w[j] = 1;

        }
}
void decomp(int x)
{
    int i;
    for(i = 1; p[i] * p[i] * 1LL <= x; ++ i)
        if(x % p[i] == 0)
    {
        while(x % p[i] == 0)
            x /= p[i];
        d[++ d[0]] = p[i];
    }
    if(x != 1LL)
        d[++ d[0]] = x;
}

long long pinex(long long a)
{
    int i, j, nr;
    long long sol = a, prod;
    for(i = 1; i < (1 << d[0]); ++ i)
    {
        nr = 0;
        prod = 1;
        for(j = 0; j < d[0]; ++ j)
            if(i & (1 << j))
        {
            ++ nr;
            prod *= d[j + 1];
        }
        if(nr % 2)
            sol -= (a / prod);
        else sol += (a / prod);

    }
    return sol;
}
long long bsearch()
{
    long long i = 0, p = 1LL * 2 * (1 << 30) * (1 << 30);
    while(p)
    {
        if (p == 8)
        {
            int ghh = 0;
            int f = 0;
        }
        if(pinex(i + p) < P)
            i += p;
        p /= 2;
    }
    return i + 1;
}
void solve()
{
    sieve();
    decomp(N);
    Sol = bsearch();
}
void write()
{
    printf("%lld\n", Sol);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}