#include <fstream>
#include <cmath>
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
unsigned long long st,dr,m,n,p,q,pp,b1,ji,j,k,a[10000000],v[10000000],s,i,t[10000000],d,r;
int main()
{f>>n>>pp;
st=1;
dr=99999999999999999;
k=0;
for(i=2;i<=1000000;i++)
{
    if(t[i]==0)
    {k++;v[k]=i;
    for(j=i;j*i<=1000000;j++)
        t[j*i]=1;
    }
}
while(st<=dr)
{
    m=(st+dr)/2;
    k=0;j=1;p=1;
    while(v[j]<=sqrt(n))
    {
        if(n%v[j]==0){b1=n;while(b1%v[j]==0){p=p*v[j];b1=b1/v[j];}k++;a[k]=v[j];}
        j++;
    }
    if(n/p!=1){k++;a[k]=n/p;}
    s=0;
    for(j=1;j<(1<<k);j++)
    {p=1;q=0;
        for(ji=1;ji<=k;ji++)
        {
            if(j&(1<<(ji-1))){p=p*a[ji];q++;}
        }
    if(q%2==0)s=s-m/p;
    else s=s+m/p;
    }
    if(m-s>pp)dr=m-1;
    if(m-s<pp)st=m+1;
    if(m-s==pp)
    {while(1>0)
        {d=m;
        i=n;r=d%i;
        while(r!=0)
        {
            d=i;
            i=r;
            r=d%i;
        }
        if(i==1){g<<m;break;}
        m--;
    }
    break;

    }
}
    return 0;
}