#include <stdio.h>
using namespace std;
long long n;
int p[2000],k=0;
long long sol(long long a){
    int i=2,nr=1;
    long long prod=1,s=0;
    for(i=0;i<(1<<k);i++){
        prod=1;
        nr=0;
        for(int j=0;j<k;j++)
            if(i&(1<<j)){
                prod*=p[j];
                nr++;
            }
        if(nr%2==0)
            s+=a/prod;
        else
            s-=a/prod;
    }
    return s;
}
long long calc(long long x){
    long long i=0,pas=1LL<<61;
    while(pas!=0){
        if(sol(i+pas)<x)
            i+=pas;
        pas>>=1;
    }
    return i+1;
}
int main(){
    long long b, i=2;
    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);
    scanf("%lld %lld",&n,&b);
    while(n!=1){
        if(n%i==0){
            while(n%i==0)
                n/=i;
            p[k++]=i;
        }
        i++;
    }
    printf("%lld",calc(b));
    return 0;
}