#include <bits/stdc++.h>

using namespace std;

ifstream f("frac.in");
ofstream g("frac.out");

unsigned long long int n,p,drv[30],nr=0,st,dr,rasp,mid,val;
unsigned long long int put=1,numar,prod,ct,fin;

int rez(unsigned long long int r)
 {
  unsigned long long int sum=0;
  for(long long int i=1;i<=put;i++)
   {
    unsigned long long int cpy=i;
    numar=0; prod=1; ct=0;
    while(cpy!=0)
     {
      ct++;
      if(cpy%2==1)
       {
        numar++;
        prod*=drv[ct];
       }
      cpy/=2;
     }
    if(r>=prod)
    {
    if(numar%2==1)
     sum+=r/prod;
    else
     sum-=r/prod;
    }
   }
  return r-sum;
 }
int main()
{
f>>n>>p;
for(long long int i=2;i*i<=n;i++)
 if(n%i==0)
  {
   nr++;
   drv[nr]=i;
   while(n%i==0)
    n/=i;
  }

if(n!=1)
 {
  nr++;
  drv[nr]=n;
 }
st=1;
dr=1;
for(int i=1;i<=61;i++)
 dr*=2;
dr--;
for(int i=1;i<=nr;i++)
  put*=2;
put--;
rasp=dr;
while(st<=dr)
 {
  mid=(st+dr)/2;
  fin=rez(mid);
  if(fin>=p) {
              if(fin==p)
               rasp=mid;
              dr=mid-1;
             }
  else st=mid+1;
 }
g<<rasp;
}