#include <stdio.h>
#define MAXP 10
int p, v[MAXP];
inline long long cate(long long e){
    int i, semn, j;
    long long x, ans=e;
    for(i=1; i<(1<<p); i++){
        semn=1;
        x=1;
        for(j=0; j<p; j++){
            if(((1<<j)&i)!=0){
                x*=v[j];
                semn*=-1;
            }
        }
        ans+=semn*(e/x);
    }
    return ans;
}
int main(){
    long long rez, pas, n, k, div;
    FILE *fin, *fout;
    fin=fopen("frac.in", "r");
    fout=fopen("frac.out", "w");
    fscanf(fin, "%lld%lld", &n, &k);
    div=2;
    p=0;
    while(div*div<=n){
        if(n%div==0){
            v[p++]=div;
            while(n%div==0){
                n/=div;
            }
        }
        div++;
    }
    if(n!=1){
        v[p++]=n;
    }
    rez=0;
    for(pas=1LL<<60; pas!=0; pas>>=1){
        if(cate(rez+pas)<k){
            rez+=pas;
        }
    }
    fprintf(fout, "%lld\n", rez+1);
    fclose(fin);
    fclose(fout);
    return 0;
}