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

#define ll long long

using namespace std;

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

ll N, P;
vector <int> D;

ll Nr(ll A)
{
    int n = D.size();
    int confmax = (1LL << n);

    ll sol = 0;
    for(int conf = 1; conf < confmax; conf++)
    {
        ll nr = 1, semn = -1;
        for(int j = 0; j < n; j++)
            if(conf & (1LL << j))
            {
                nr *= 1LL * D[j];
                semn *= -1;
            }
        sol += 1LL * semn * A / nr;
    }
    return (A - sol);
}

int main()
{
    fin >> N >> P;
    for(int i = 2; i * i <= N; i++)
        if(N % i == 0)
        {
            D.push_back(i);
            while(N % i == 0)
                N /= i;
        }
    if(N > 1) D.push_back(N);

    ll st = 0, dr = (1LL << 61);

    while(dr - st > 1)
    {
        ll mid = (st + dr) >> 1;
        ll val = Nr(mid);
        if(val < P)
            st = mid;
        else
            dr = mid;
    }
    fout << dr;
    return 0;
}