#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

vector<long long> Diviz;
long long N, P, sol;

long long pinex(long long a)
{
    long long D = a, lim = (1 << Diviz.size()), k, mc;
    for(int i = 1; i < lim; ++i)
    {
        k = 0, mc = 1;
        for(int j = 0; (1 << j) <= i; ++j)
            if(i & (1 << j))
            {
                k++;
                mc *= Diviz[j];
            }
        if(k % 2 == 0) D += a / mc;
        else D -= a / mc;
    }
    return D;
}
void divizori()
{
    for(long long d = 2; d * d <= N; ++d)
        if(N % d == 0)
        {
            Diviz.push_back(d);
            while(N % d == 0)
                N /= d;
        }
    if(N > 1)
        Diviz.push_back(N);
}

int main()
{
    f >> N >> P;
    divizori();
    long long st = 1, dr = (1LL << 61), mij;
    while(st <= dr)
    {
        mij = (st + dr) / 2;
        if(P <= pinex(mij))
            sol = mij, dr = mij - 1;
        else st = mij + 1;
    }
    g << sol;
    f.close();
    g.close();
    return 0;
}