#include <cstdio>
#define INF 2305843009213693952

using namespace std;
long long v[1000],m;
int b[1000];
long long afla (long long n,long long mid){
    // cate numere mai mici sau egale cu mid sunt prime intre ele cu n
    long long i=0,s=0,nru,p;
    b[0]=0;
    nru=0;
    p=1;
    i=m;
    while (!b[0]){
        i=m;
        while (b[i]==1){
            p/=v[i];
            nru--;
            b[i]=0;
            i--;
        }
        nru++;
        b[i]=1;
        p*=v[i];
        if (i==0)
            break;
        if (nru%2==1)
            s+=(mid/p);
        else s-=(mid/p);
    }
    return mid-s;
}
long long cmmdc (long long a,long long b){
    long long r=0;
    while (b>0){
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main()
{
    FILE *fin=fopen ("frac.in","r");
    FILE *fout=fopen ("frac.out","w");
    long long n,p,st,dr,mid,nr,d=2,e,i=0,n2;
    fscanf (fin,"%lld%lld",&n,&p);
    n2=n;
    while (d*d<=n){
        e=0;
        while (n%d==0){
            e++;
            n/=d;
        }
        if (e)
            v[++i]=d;
    }
    if (n!=1)
        v[++i]=n;
    m=i;
    st=1;
    dr=INF;
    while (st<=dr){
        mid=(st+dr)/2;
        nr=afla (n,mid);
        //if (mid==16)
          //  printf ("a");
        if (nr>p)
            dr=mid-1;
        else if (nr<p)
            st=mid+1;
        else if (nr==p){
            if (cmmdc (mid,n2)==1){
                fprintf (fout,"%lld",mid);
                break;
            }
            else dr=mid-1;
        }
    }
    return 0;
}