#include <iostream>
#include<cstdio>
using namespace std;
long long divprimi[100];
const int N=1000001;
long long rezolva(long long a){
  long long i;
  long long nrnp=0;
  long long j;
  long long nringrup;
  long long m=1;
  for(i=1;i<(1<<(divprimi[0]));i++){
    nringrup=0;
    m=1;
    for(j=0;j<=divprimi[0]-1;j++){
      if((i&(1<<j))>0){
        nringrup++;
        m=(long long)m*divprimi[j+1];
      }
    }
    if(nringrup%2==1)
      nrnp+=(long long)a/m;
    else
      nrnp-=(long long)a/m;
  }
  return a-nrnp;
}
long long cautbin(long long p){
  long long p2=1LL<<62;
  long long pas=0;
  while(p2!=0){
    if(rezolva(pas+p2)<p)
      pas+=p2;
    p2/=2;
  }
  return pas+1;
}
int main()
{
    FILE*fin,*fout;
    long long d=2;
    long long b;
    long long p;
    fin=fopen("frac.in","r");
    fout=fopen("frac.out","w");
    fscanf(fin,"%lld%lld",&b,&p);
    while((long long)d*d<=b){
      if(b%d==0){
        divprimi[++divprimi[0]]=d;
        while(b%d==0)
          b=(long long)b/d;
      }
      d++;
    }
    if(b>1){
      divprimi[++divprimi[0]]=b;
    }
    fprintf(fout,"%lld",cautbin(p));

    return 0;
}