#include <fstream>
#include <vector>
#define INF (1LL<<61) - 1
#define ll long long

using namespace std;

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

ll n, p;

bool ciur[110002];

vector<ll> diviz;
vector<int> prime;

bool test(int a, int b){
    return (a & (1<<b));
}

ll calc(ll x){
    ll nr = 0;
    int dim = (1<<diviz.size()) - 1;
    for(int i = 1; i <= dim; ++ i){
        int cnt = 0;
        ll val = 1;
        int bits = 0;
        for(vector<ll>::iterator it = diviz.begin(); it != diviz.end(); ++ it, ++ cnt){
            if(test(i, cnt)){
                val *= (1LL * *it);
                ++ bits;
            }
        }
        if(bits % 2)
            nr += (x / val);
        else
            nr -= (x / val);
    }
    return x - nr;
}

ll cmmdc(ll a, ll b){
    ll r = a % b;
    while(r){
        a = b;
        b = r;
        r = (a % b);
    }
    return b;
}

int main(int argc, const char * argv[]) {
    in>>n>>p;
    ll N = n;
   // -- p;
    
    for(int i = 2; (1LL * i * i) <= 110000; ++ i){
        if(ciur[i]) continue;
        for(int j = i + i; j <= 110000; j += i)
            ciur[j] = true;
    }
    
    for(int i = 2; i <= 110000; ++ i)
        if(!ciur[i])
            prime.push_back(i);
    
   // diviz.push_back(1);
    for(vector<int>::iterator it = prime.begin(); it != prime.end() && *it * *it <= n; ++ it){
        if(n % *it == 0){
            while(n % *it == 0)
                n /= *it;
            diviz.push_back(*it);
        }
    }
    
    if(n)
        diviz.push_back(n);
    
    
    
    ll st = 1;
    ll dr = INF;
    //out<<calc(13);
    //out<<cmmdc(8, 12);
    while(st <= dr){
        ll mid = (st + dr) / 2;
        ll val = calc(mid);
        ll Cmmdc = cmmdc(mid, N);
        if(val == p && Cmmdc == 1){
            out<<mid;
            return 0;
        }
        if(val > p || (val == p && Cmmdc > 1))
           dr = mid - 1;
        else
           st = mid + 1;
    }
    
    return 0;
}