#include <iostream>
#include <fstream>
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
bool ok[1000005];
int varr[80005],k=0,dv=0;
long long a,b,d[1005],var1=0;

void Prog()
{
    int i,j,vmax=1000000;
    for(i=2; i<=vmax; i++)
    {
        if (!ok[i])
        {
            k++;
            varr[k]=i;
            for(j=i+i; j<=vmax; j+=i)
                ok[j]=1;
        }
    }
}

void fun(long long x)
{
    int i;
    dv=0;
    for(i=1; i<=k && x>1; i++)
    {
        if (x%varr[i]==0)
        {
            dv++;
            d[dv]=varr[i];
            while(x%varr[i]==0) x/=varr[i];
        }
        if (1LL*varr[i]*varr[i]>1LL*x) break;
    }
    if (x>1)
    {
        dv++;
        d[dv]=1LL*x;
    }

}

long long funn2(long long sol)
{
    int i,j,num=0;
    long long mult=0,sol=0;

    for(i=1; i<(1<<dv); i++)
    {
        num=0;
        mult=1;
        for(j=0; j<dv; j++)
            if (i&(1<<j))
            {
                mult*=1LL*d[j+1];
                num++;
            }
        if (num%2==1) sol+=1LL*(sol/mult);
        else sol-=1LL*(sol/mult);
    }

    return 1LL*(sol-sol);
}

void Binary()
{
    long long st=1,dr=(1LL<<61),mid=0;
    while(1LL*st<1LL*dr)
    {
        mid=1LL*(st+dr)/2;
        if (1LL*funn2(mid)>=1LL*var1) dr=1LL*mid;
        else st=1LL*(mid+1);
    }
    g<<1LL*st;
}
int main()
{
    int t;
    Prog();

    f>>b>>var1;
    fun(b);
    Binary();

    return 0;
}