#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
vector<int> div;
long long calcule(long long a)
{
    long long i,j,d,nr,rez=0;
    for(i=1;i<(1<<(int)div.size());i++)
    {
        nr=0;d=1;
        for(j=0;j<(int)div.size();j++)
                if(i&(1<<j))
                {
                    nr++;
                    d=d*div[j];
                }
        if(nr%2==0) rez-=a/d;
        else rez+=a/d;
    }
    return a-rez;
}
int main()
{
    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);
    long long CN,N,P,last,st,dr,med,x;
    scanf("%lld%lld",&N,&P);CN=N;
    long long lim,d;
    lim=(int)sqrt(1.0*N);d=2;
    while(d<=lim && N>1)
    {
        if(N%d==0) div.push_back(d);
        while(N%d==0) N/=d;
        d++;
    }
    if(N>1) div.push_back(d);
    st=0;dr=1LL<<61;last=dr;
    while(st<=dr)
    {
        med=(st+dr)/2;x=calcule(med);
        if(x==P)
            last=med,dr=med-1;
        else
            if(x>=P)
                dr=med-1;
            else st=med+1;
    }
    printf("%lld\n",last);
    return 0;
}