#include <cstdio>

#define maxS 109545

long long N, P;
long long F[maxS];

void Fact()
{
    long long f = 2;
    long long n = N;

    while(n != 1)
    {
        int ok = 0;
        while(!(n % f))
        {
            n /= f;
            ok = 1;
        }
        if(ok) F[++F[0]] = f;

        ++ f;
    }
}

long long Cmmdc(long long x, long long y)
{
    long long r;

    while(y)
    {
        r = x % y;
        x = y;
        y = r;
    }

    return x;
}

long long Euler(long long x)
{
    long long r = x;

    int i;
    for(i=1; i<=F[0]; ++i)
        r -= (r / F[i]);

    return r;
}

int main()
{
    freopen("frac.in", "rt", stdin);
    freopen("frac.out", "wt", stdout);

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

    long long st = 1, dr = (long long) 1 << 62, m;

    while(st <= dr)
    {
        m = (st + dr) >> 1;

        if(Cmmdc(m, N) == 1)
        {
            long long r = Euler(m);

            if(r == P)
            {
                printf("%lld", m);
                break;
            }
            else
            {
                if(r < P) st = m + 1;
                if(r > P) dr = m - 1;
            }
        }
        else
            -- dr;
    }

    fclose(stdin);
    fclose(stdout);

    return 0;
}