#include <fstream>

using namespace std;

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

long long sol[2000];
long long nrfac;

long long rez(long long x) {
    long long z = x, nr, prod, i, j;
    for ( i = 1; i < (1 << nrfac); i++ ) {
      nr = 0;
      prod = 1;
      for ( j = 0; j < nrfac; j++ ) {
        if ( (i & (1 << j)) != 0 ) {
          nr++;
          prod = prod * sol[j + 1];
        }
      }
      if ( nr % 2 == 1 )
        z = z - x / prod;
      else
        z = z + x / prod;
    }
    return z;
}

int main()
{
    long long n, p, ct, st, dr, mij;
    fin >> n >> p;
    ct = 2;
    while ( ct * ct <= n && n > 1 ) {
      if ( n % ct == 0 ) {
        sol[++nrfac] = ct;
        while ( n % ct == 0 )
          n = n / ct;
      }
      ct++;
    }
    if ( n > 1 )
      sol[++nrfac] = n;
    st = 1;
    dr = (1LL << 61);
    while ( st <= dr ) {
      mij = (st + dr) / 2;
      if ( rez(mij) < p )
        st = mij + 1;
      else
        dr = mij - 1;
    }
    fout << st;
    return 0;
}