#include <fstream>
#include <vector>
#include <cmath>
#define amax 110005
using namespace std;
vector <long long> Dp;
vector <long long> diviz;
vector <bool> semn;
long long st[amax],fprimi[amax];bool prim[amax];
long long dim,fp;
void precalcul()
{
    long long d,i;
    for (d=2;d<amax;d++)
    {
        if (!prim[d])
        {
            fprimi[++fp]=d;
            for (i=2*d;i<amax;i+=d)
                prim[i]=1;
        }
    }
}
void desc(long long x)
{
    long long d,y;
    Dp.clear();
    for (d=1; d<=fp && x!=1 ;d++)
    {
        y=fprimi[d];
        if (x%y==0)
        {
            Dp.push_back(y);
            while (x%y==0) x/=y;
        }
    }
    if (x!=1) Dp.push_back(x);
    dim=Dp.size();
}
void divizori()
{
    long long i,p=1,prod=1;
    st[p]=0;
    while (p>0)
    {
        if (st[p]<dim)
        {
            st[p]++;
            {
                for (i=1,prod=1;i<=p;i++)
                    prod*=(Dp[st[i]-1]);
                diviz.push_back(prod);
                if (p%2) semn.push_back(true);
                else semn.push_back(false);
            }
            if (p<dim)
                st[++p]=st[p-1];
        }
        else p--;
    }
}
long long cate(long long x)
{
    long long i,s=0;
    for (i=0;i<diviz.size();i++)
    {
        if (semn[i]) s+=(x/diviz[i]);
        else s-=(x/diviz[i]);
    }
    return (x-s);
}
int main()
{
    ifstream fin("frac.in");
    ofstream fout("frac.out");
    precalcul();
    long long b,i,p,a=1;
    fin>>b>>p;
    desc(b);divizori();
    a<<=61;
    for (i=0;a;a>>=1)
        if (cate(i+a)<p)
            i+=a;
    fout<<i+1<<'\n';
    fin.close();
    fout.close();
    return 0;
}