#include <cstdio>

#define maxS 109545

long long N, P, FN;

double 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[++FN] = 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<=FN; ++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 i = 0, step = (long long) 1 << 62;
    double p = P;

    for(; step; step>>=1)
        if(Euler(i+step) <= p) i += step;

    while(Euler(i) < p) ++ i;

    while(Cmmdc(i, N) != 1) -- i;

    printf("%lld", i);

    fclose(stdin);
    fclose(stdout);

    return 0;
}