#include<fstream>

using namespace std;

ifstream f("frac.in");
ofstream g("frac.out");

//ifstream f("in.in");
//ofstream g("out.out");

long long n,p;
long long d,k = 0,v[105];
long long nr,i,cnt,prod,j;
long long st,dr,mid,solNr;

bool sol(long long m){
    //cout<<m<<" ";

    nr = 0;
    ///generare
    for(i=1;i<(1<<k);i++){
        cnt=0;prod=1;
        for(j=0;j<k;j++){
            if( (i>>j)&1 ){
                prod*=v[j+1];
                cnt++;
            }
        }

        ///includere/excludere
        //cout<<"|"<<prod<<"|";
        if(cnt != 0){
            if(cnt%2 == 1){
                nr+=m/prod;
            }else{
                nr-=m/prod;
            }
        }
    }
    if(nr>0){
        m = m-nr;
    }else{
        m = m+nr;
    }

    return m>=p;
}

int main(){

    f>>n>>p;

    d = 2;
    while(d*d<=n && n!=1){
        bool ok = 0;
        while(n%d == 0){
            ok=1;
            n/=d;
        }
        if(ok == 1){
            k++;
            v[k] = d;
        }
    }
    if(n!=1){
        k++;
        v[k] = n;
    }

    st=1;
    dr=(1LL<<61);
    solNr = -1;

    while(st<=dr){
        mid = (st+dr)/2;
        //cout<<mid<<": ";
        if(sol(mid) == 1){
            solNr = mid;
            dr = mid-1;
        }else{
            st = mid+1;
        }
    }
    g<<solNr;

    f.close();
    g.close();
    return 0;
}