#include <fstream>

#define ll long long
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
ll N,P,D[20],nrdiv;
void read()
{
    fin>>N>>P;
}
void prep(long long nr)
{
    for(ll i=2;i*i <= nr;i++)
        if(nr%i==0)
        {
            D[++nrdiv] = i;
            while(nr%i==0)
                nr/=i;
        }
    if(nr!=1)
        D[++nrdiv] = nr;
}
ll compute(ll val)
{
    ll i,j,pr,sol = val;
    for(i=1;i<(1<<nrdiv);i++)
    {
        pr = 1;
        for(j=0;j<=nrdiv;j++)
            if((i&(1<<j))>0)
                pr *= -D[j+1];
        sol+=val/pr;
    }
    return sol;
}
ll solve()
{
    ll st = 1, dr = (1ll<<61),mid;
    while(st<=dr)
    {
        mid = (st+dr)/2;
        if(compute(mid) < P)
            st = mid+1;
        else
            dr = mid-1;
    }
    return st;
}
int main()
{
    read();
    prep(N);
    fout<<solve();
    return 0;
}