#include <cstdio>
using namespace std;
long long n,b,i=2;
int p[2000],k=0;
long long sol(long long a)
{
int nr,j;
long long pr=1,rasp=0;
for (i=0;i<(1<<k);i++)
    {
    pr=1;nr=0;
    for (j=0;j<k;j++)
    if(i&(1<<j)) {
                  pr*=p[j];
                  nr++;
                 }
    if (nr%2==0) rasp+=a/pr;
            else rasp-=a/pr;
    }
    return rasp;
}
long long calc(long long x)
{
long long i=0,pas=1LL<<61;
while (pas)
    {
    if (sol(i+pas)<x) i+=pas;
    pas/=2;
    }
return i+1;
}
int main()
{
freopen("frac.in","r",stdin);
freopen("frac.out","w",stdout);
scanf("%lld %lld",&n,&b);
while(n>1)
    {
    if(n%i==0)
         {
         while(n%i==0) n/=i;
         p[k++]=i;
         }
    i++;
    }
printf("%lld",calc(b));
return 0;
}