#include<fstream>
#include<iostream>

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,v[50];
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) == 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;
    }

    //cout<<m<<"="<<nr<<" (";
    if(m>=p){
        //cout<<"1)\n";
        return 1;
    }
    //cout<<"0)\n";
    return 0;
}

int main(){

    f>>n>>p;

    d = 2;
    while(d*d<=n && n!=1){
        if(n%d == 0){
            k++;
            v[k] = d;
            while(n%d == 0){
                n/=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;
}