#include <fstream>
#include<vector>
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
long long n,m,x,k,p;
vector<int> divv;
long long rez(long long x)
{
    long long sol=0;
    long long nr=divv.size();
    for(long long i=1; i<(1<<nr) ;i++)
    {
            k=0;
            p=1;
            for(long long j=0;j<nr;j++)
            {
               if((1<<j)&i)
               {
                   p=p*divv[j];
                   k++;
               }
            }
            if(k%2)
                sol=sol+x/p;
            else
                sol=sol-x/p;
    }
    return x-sol;
}
int main()
{
    fin>>n>>m;
    x=n;
    for(int d=2;d*d<=x;d++)
    {
        if(x%d==0)
        {
            divv.push_back(d);
            while(x%d==0)
                x/=d;
        }
    }
    if(x!=1)
        divv.push_back(x);

    long long st=1;
    long long dr=(1ll<<61);
    long long mid,val;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        val=rez(mid);
        if(val>=m)
            dr=mid-1;
        else
            st=mid+1;
    }
    fout<<st;
    return 0;
}