#include <fstream>
#include <vector>
#include <iomanip>
#include <map>
#define ll long long
using namespace std;
ifstream cin("frac.in");
ofstream cout("frac.out");
vector<ll> primes;
ll sum, ans, cnt;
ll a, b;
void bkt(ll pas, ll a)
{
    if(pas == primes.size())
    {
        if(cnt == 0)
            return;
        if(cnt % 2 == 0)
            sum -= a / ans;
        else
            sum += a / ans;
        return;
    }
    cnt++;
    ans *= primes[pas];
    bkt(pas + 1, a);
    ans /= primes[pas];
    cnt--;
    bkt(pas + 1, a);
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll m;
    ll b, p;
    cin>>b>>p;\
    for(int d = 2; d * d <= b; d++)
    {
            ll e = 0;
            while(b % d == 0)
                b /= d, e++;
            if(e > 0)
                primes.push_back(d);
    }
    if(b > 1)
        primes.push_back(b);
    ll st = 1, dr = 1ll << 61;
    ll anss = 0;
    while(st <= dr)
    {
        ll mid = (st + dr) / 2;
        ans = 1;
        cnt = 0;
        sum = 0;
        bkt(0, mid);
        ///mid - sum
        if(mid - sum == p - 1)
        {
            anss = mid + 1;
            break;
        }
        if(mid - sum < p)
            st = mid + 1;
        else
            dr = mid - 1;
    }
    cout<<anss;
    return 0;
}