#include <bits/stdc++.h>

using namespace std;

typedef long long lld;

vector < lld > fact;

inline lld coprimes(lld lim) {
  lld ans = lim;
  for (int conf = 1; conf < (1 << (int) fact.size()); ++conf) {
    int sgn = 1, cmmmc = 1;
    for (int b = 0; b < (int) fact.size(); ++b)
      if (conf & (1 << b)) {
        sgn = -sgn;
        cmmmc *= fact[b];
      }
    ans += lim / cmmmc * sgn;
  }
  return ans;
}

int main()
{
    lld n, p, ans = 0;
    ifstream fin("frac.in");
    fin >> n >> p;
    fin.close();
    for (lld d = 2; d * d <= n; ++d)
      if (n % d == 0) {
        fact.push_back(d);
        while (n % d == 0)
          n /= d;
      }
    if (n > 1)
      fact.push_back(n);
    for (lld step = 1LL << 61; step > 0; step >>= 1)
      if (coprimes(ans + step) < p)
        ans += step;
    ofstream fout("frac.out");
    fout << ans + 1 << '\n';
    fout.close();
    return 0;
}