#include <cstdio>
#include <algorithm>
using namespace std;

int NR, CR = 0;
long long Sol, mij, Prod, n, m, divi[1000];
inline void back(int k){
    if(k == NR){
        if(CR % 2 == 0)Sol = Sol + mij / Prod;
        else Sol = Sol - mij / Prod;
        return ;
    }
    back(k + 1);
    Prod *= divi[k + 1];
    ++CR;
    back(k + 1);
    --CR;
    Prod /= divi[k + 1];
}
int main()
{
    freopen("frac.in", "r", stdin);
    freopen("frac.out", "w", stdout);
    scanf("%lld%lld", &n, &m);
    NR = 0;
    if(n % 2 == 0){
        while(n % 2 == 0) n = n / 2;
        divi[++NR] = 2;
    }
    long long d = 3;
    long long aux = n;
    while(d * d * 1LL < aux){
        if(n % d == 0){
            divi[++NR] = d;
            while(n % d == 0) n = n / d;
        }
        d += 2;
    }
    if(n > 1) divi[++NR] = n;
    long long afis, st = m, dr = (long long)((long long)1 << 61);
    while(st <= dr){
        mij = (st + dr) / 2;
        Sol = 0;
        Prod = 1; CR = 0;
        back(0);
        if(Sol >= m){
            dr = mij - 1;
            afis = mij;
        }
        else if(Sol < m) st = mij + 1;
    }
    printf("%lld", afis);
    return 0;
}