#include <cstdio>
#include <vector>

typedef long long i64;
#define MAXR 1LL << 62

std::vector <int> a;

i64 check(i64 x) {
  int n = a.size();
  bool sgn;
  i64 f, r = 0;
  for (int i = 1; i < (1 << n); ++i) {
    f = 1;
    sgn = 1;
    for (int j = 0; j < n; ++j) {
      if (i & (1 << j)) {
        f *= 1LL * a[j];
        sgn ^= 1;
      }
    }
    r += !sgn ? x / f : -x / f;
  }
  return x - r;
}

int main() {
  i64 n, p, cn, ans;
  int d;
  FILE *f = fopen("frac.in", "r");
  fscanf(f, "%lld%lld", &n, &p);
  fclose(f);
  cn = n;
  d = 2;
  while (1LL * d * d <= cn) {
    if (!(cn % d)) {
      a.push_back(d);
      while (!(cn % d)) {
        cn /= d;
      }
    }
    ++d;
  }
  if (cn != 1) {
    a.push_back(cn);
  } 
  ans = 0LL;
  for (i64 i = MAXR; i > 0; i >>= 1) {
    if (check(ans + i) < p) {
      ans += i;
    }
  }
  f = fopen("frac.out", "w");
  fprintf(f, "%lld\n", ans + 1);
  fclose(f);
  return 0;
}