#include<fstream>
#include<algorithm>
using namespace std;
ifstream cin("frac.in");
ofstream cout("frac.out");
long long n,p,x[1000005],k;
long long cp(long long a){
    long long rez=a;
    for(int i=1;i<(1<<k);i++){
        long long prod=1,nr=0;
        for(int j=0;j<k;j++)
            if((1<<j)&i){
                prod=1LL*prod*x[j + 1];
                ++nr;
            }
        if(nr%2) nr=-1;
        else nr=1;
        rez=rez+1LL*nr*a/prod;
    }
    return rez;
}
int main(){
    cin>>n>>p;
    if(n%2==0){
        x[++k]=2;
        while(n%2==0) n/=2;
    }
    for(int d=3;1LL*d*d<=n;d+=2)
        if(n%d==0){
            x[++k]=d;
            while(n%d==0) n/=d;
        }
    if(n>1) x[++k]=n;
    long long ans=0,step=(1LL<<61),lim=step;
    while(step){
        if(ans+step<=lim && cp(ans+step)<p)
            ans+=step;
        step>>=1;
    }
    cout<<ans+1;
}