#include <fstream>
#include <vector>
#define ll long long
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
ll n, p;
vector <ll> div;
void divizori(ll x)
{
    ll d = 2;
    if(x % d == 0)
    {
        while(x % d == 0)
            x /= d;
        div.push_back(d);
    }
    d = 3;
    while(d * d <= x && x > 1)
    {
        if(x % d == 0)
        {
            while(x % d == 0)
                x /= d;
            div.push_back(d);
        }
        d += 2;
    }
    if(x > 1) div.push_back(x);
}
ll pinex(ll x)
{
    ll ans, maxim;
    ans = 0;
    maxim = 1LL << div.size();
    for(ll i = 0; i < maxim; ++i)
    {
         ll prod = 1;
         ll nr = 0;
         for(ll j = 0; j < div.size(); ++j)
            if(i & (1LL << j))
             {
                 nr++;
                 prod *= div[j];
             }
        if(nr % 2 == 0)
            ans += x / prod;
        else ans -= x/ prod;
    }
    return ( x - ans >= p);
}
int main()
{
    f >> n >> p;
    divizori(n);
    ll st = 1, dr = (1LL << 61), last = 1;
    while(st <= dr)
    {
        ll mij = (st + dr)/ 2 ;
        if(pinex(mij))
            dr = mij - 1, last = mij;
        else st = mij + 1;
    }
    g << last;
    f.close(); g.close();
    return 0;
}