#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ullong;

ullong N, P;

vector<size_t> D;

ullong pinex(ullong A)
{
    ullong answer = A;

    for(ullong i = 1; i < ullong(1 << D.size()); ++i)
    {
        ullong contor = 0;
        ullong produs = 1;

        for(size_t j = 0; j < D.size(); ++j)
        {
            if(i & (1 << j))
            {
                contor++;
                produs = 1LL * produs * D.at(j);
            }
        }

        if(contor % 2) answer -= A / produs;
        else answer += A/produs;
    }

    return answer;
}
ullong cautBin()
{
   ullong stanga = 1, dreapta = ullong(1LL*1 << 61), mid;

   while(stanga <= dreapta)
   {
       mid = (stanga + dreapta)/2;

       ullong midRez = pinex(mid);

       if(midRez == P)
       {
            ullong prevMidRez = pinex(mid - 1);
            if(prevMidRez < P) return mid;
       }

       if(midRez >= P) dreapta = mid - 1;
       else stanga = mid + 1;
   }

   return 0;
}

int main()
{
    ifstream fin("frac.in");
    ofstream fout("frac.out");

    fin >> N >> P;

    ullong copyN = N;

    size_t div = 2;


    while(N - 1)
    {
        if(!(N % div))
        {
            D.push_back(div);
            while(!(N % div)) N /= div;
        }

        ++div;

        if(div * div > N) div = N;
    }


    N = copyN;

    fout << cautBin();
}