#include <stdio.h>

using namespace std;

FILE*f=fopen("frac.in","r"),*g=fopen("frac.out","w");
long long n, k, div[1000], u;

void descompunere(long long a)
{
    long long i = 2, x = a;
    while(i*i <= a )
    {
        if(x%i == 0)
        {
            div[++u] = i;
        }
        while(x % i == 0)
        {
            x /= i;
        }
        i++;
    }
    if(x != 1)
        div[++u] = x;
}

long long primi(long long x)
{
    long long sol = 0;
    long long maxim = (1 << u);
    for(long long i = 1; i < maxim; i++)
    {
        long long p = 1;
        int nr = 0;
        for(long long j = 0; j < u; j++)
        {
            if(i & (1 << j))
            {
                nr++;
                p *= div[j+1];
            }
        }
        if(nr % 2 == 0)
        {
            sol -= x/p;
        }
        else sol += x/p;
    }

    return x - sol;
}

long long cmmdc(long long a, long long b)
{
    long long c;
    while(b)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int main()
{
    fscanf(f,"%lld %lld\n",&n,&k);
    descompunere(n);
    long long p, u, mij, rasp = 0;
    p = 1;
    u = (1ll << 62);
    while(p <= u)
    {
        mij = ((p+u) >> 1);
       long long sol = primi(mij);
        if(sol > k)
        {
            u = mij - 1;
        }
        else if(sol < k)
        {
            p = mij + 1;
        }
        else if(k == sol)
        {
            if(cmmdc(mij,n) == 1)
            {
                rasp = mij;
                break;
            }
            else u = mij - 1;
        }
    }
    fprintf(g,"%lld\n",rasp);
    return 0;
}