#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) 10.e20, m;

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

//        if(Cmmdc(m, N) == 1)
//        {
            double r = Euler(m);
            double p = P;

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

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

    fclose(stdin);
    fclose(stdout);

    return 0;
}