#include <stdio.h>
int d[50],nrd;
long long cate(long a, long long b){
    long long i,j,nr,s=0,val;
    for(i=0;i<(1<<nrd);i++){
        val=1;
        nr=0;
        for(j=0;j<nrd;j++)
            if(i&(1<<j)){
                val=val*(long long)d[j];
                nr++;
            }
        if(nr%2==0)
            s+=a/val;
        else
            s-=a/val;
    }
    return s;
}
void divizori(long long b){
    long long i,c=b;
    for(i=2;i*i<=b;i++)
        if(b%i==0){
            d[nrd]=i;
            nrd++;
            while(c%i==0)
                c=c/i;
        }
    if(c!=1){
        d[nrd]=c;
        nrd++;
    }
}
bool prim(long long a,long long b){
    long long r;
    while(b!=0){
        r=a%b;
        a=b;
        b=r;
    }
    if(a==1)
        return true;
    return false;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("frac.in","r");
    fout=fopen("frac.out","w");
    long long a,b,st,dr,n,rasp=0;
    fscanf(fin,"%lld%lld",&b,&n);
    divizori(b);
    st=1;
    dr=((long long)1<<61);
    while(st<=dr){
        a=(st+dr)/2;
        if(cate(a,b)<n){
            st=a+1;
        }
        else{
            rasp=a;
            dr=a-1;
        }
    }
    while(prim(rasp,b)==false)
        rasp++;
    fprintf(fout,"%lld",rasp);
    fclose(fin);
    fclose(fout);
    return 0;
}