using namespace std;
#include<fstream>
#include<stdio.h>
#include<math.h>

int d[100],nd;

long long f(long long x)
{
//divizorii primi
long long sol=0,i;
int conf,diviz,n1; 

for(conf=1;conf< (1<<nd);conf++)
   {
   diviz=1;
   n1=0;
   
   for(i=0;i<nd;i++)
     if( ((1<<i) & conf) )
        {
        diviz*=d[i+1];  
        n1++;
        }
   
   if(n1%2)
      sol+=x/diviz;
   else
      sol-=x/diviz;
   }
     
return x-sol;
}     

int main()
{
FILE *fout=fopen("frac.out","w");
ifstream fin("frac.in");
     
long long N,P;
int i;
fin>>N>>P;

nd=0;
if(N%2==0)
   {
   d[++nd]=2;
   while(N%2==0)
      N>>=1;
   }

for(i=3;i<=(long long)sqrt((double)N);i+=2)
   if(N%i == 0)
      {
      d[++nd]=i;
      while(N%i==0)
         N/=i;
      }
      
if(N!=1)
  d[++nd]=N;


long long li,lf,mij,sol;
li=1;lf=((long long)1<<50);

while(lf-li>1)
  {
  mij=(li+lf)>>1;
  
  sol=f(mij);
  if(sol<P)
     li=mij;
  else
     lf=mij;  
  }
  
if(f(li)==P)
   fprintf(fout,"%lld\n",li);
else
   fprintf(fout,"%lld\n",lf);

fin.close();   
fclose(fout);
return 0;         
}