#include <fstream>
#define ll long long
using namespace std;
ifstream f("frac.in"); ofstream g("frac.out");
ll k,prim[11];
ll rez(ll x)
{   ll nr=x;
    for(int i=1;i<(1LL<<k);i++)
    {   ll q=0,p=1;
        for(ll j=0;j<k;j++)
            if(i&(1LL<<j)) {q++; p=p*prim[j+1];}
        if(q%2) nr-=x/p; else nr+=x/p;
    }
    return nr;
}
int main()
{   ll n,p;
    f>>n>>p;
    ll d=2;
    while(d*d<=n)
    {   if(n%d==0)
        {   prim[++k]=d;
            while(n%d==0) n/=d;
        }
        d++;
    }
    if(n>1) prim[++k]=n;
    ll st=1,dr=(1LL<<61);
    while(st<=dr)
    {   ll m=(st+dr)/2;
        if(rez(m)<p) st=m+1; else dr=m-1;
    }
    g<<st; g.close(); f.close(); return 0;
}