#include<cstdio>
using namespace std;

long long fact[1005];
int nrfact;

void descompunere(long long n){
    if(n%2==0){
        fact[++nrfact]=2;
        while(n%2==0)
            n/=2;
    }
    for(int d=3;d*d<=n && n>1;d+=2)
        if(n%d==0){
            fact[++nrfact]=d;
            while(n%fact[nrfact]==0)
                n/=fact[nrfact];
        }
    if(n>1)
        fact[++nrfact]=n;
}

long long pinex(long long nr){
    long long put=(1<<nrfact),s=0;
    for(long long v=1;v<put;v++){
        long long prod=1,paritate=0;
        for(int i=0;i<nrfact;i++)
            if(v & (1<<i)){
                prod*=fact[i+1];
                paritate++;
            }
        if(paritate%2==1)
            s+=nr/prod;
        else
            s-=nr/prod;
    }
    return nr-s;
}

int main(){
    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);
    long long n,p,valoare=1,st=0,dr,mij;
    scanf("%lld%lld", &n, &p);
    descompunere(n);
    dr=1LL<<61;
    while(st<dr){
        mij=dr-(dr-st)/2;
        long long pp=pinex(mij);
        if(pp>p)
            dr=mij-1;
        else
            if(pp<p)
                st=mij+1;
            else
                break;
    }
    while(pinex(mij)==p)
        mij--;
    mij++;
    printf("%lld", mij);
    return 0;
}