#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

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

vector <int> prime;
vector <long long> divi;

void ciurr()
{
    bitset<1000001> ciur;

    for (int i = 2; i * i <= 1000001; i++)
        if (!ciur[i])
            for (int j = i * i; j <= 1000001; j++)
                ciur[j] = 1;

    for (int i = 2; i <= 1000001; i++)
        if (!ciur[i])
            prime.push_back(i);
}

void desc(unsigned long long n)
{
    ciurr();

    unsigned long long i = 0;
    while (i < prime.size() && prime[i] * prime[i] <= n)
    {
        if (n % prime[i] == 0)
        {
            divi.push_back(prime[i]);

            while (n % prime[i] == 0)
                n /= prime[i];
        }
        
        i++;
    }

    if (n != 1)
        divi.push_back(n);
}

unsigned long long pinex(unsigned long long a)
{
    unsigned int n = divi.size();
    long long rez = 0;

    for (unsigned long long i = 0; i < (1 << n); i++)
    {
        unsigned long long nr = 0;
        unsigned long long p = 1;

        for (unsigned long long j = 0; j < n; j++)
        {
            if (i & (1 << j))
            {
                nr++;
                p *= divi[j];
            }
        }

        if (nr % 2 == 0)
            rez += a / p;
        else
            rez -= a / p;
    }

    return rez;
}

unsigned long long caut_bin(unsigned long long p)
{
    unsigned long long st = 1;
    unsigned long long dr = 1LLU << 61;

    while (st <= dr)
    {
        unsigned long long m = (st + dr) / 2;

        if (pinex(m) > p)
            dr = m - 1;
        else
            st = m + 1;
    }

    return st;
}

int main()
{
    unsigned long long n, p;
    f >> n >> p;

    desc(n);
    unsigned long long ans = caut_bin(p-1);

    g << ans << '\n';

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