#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;
}

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

    int i;
    for(i=1; i<=F[0]; ++i)
        r -= (double) (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 = 0, dr = (long long) 1 << 61, m;
    double p = P;

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

        double r = Euler(m);

        if(r == p)
        {
//            while(Cmmdc(m, N) != 1) -- m;

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

    fclose(stdin);
    fclose(stdout);

    return 0;
}