#include<fstream>
#include<stdio.h>
#include<math.h>
using namespace std;
int d[100],nd;
long long f(long long x){
long long sol=0,i,diviz;
int conf,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<<51);
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;
}