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

using namespace std;

vector<int> factori;
long long fp[1 << 12];

void factorize(long long n) {
  for (long long i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      factori.push_back(i);
      while (n % i == 0) n /= i;
    }
  }
  if (n != 1) factori.push_back(n);
}

int relprime(long long x) {
  for (int i = 0; i < factori.size(); ++i) {
    if (x % factori[i] == 0) return false;
  }
  return true;
}

long long get_ord(long long m) {
  long long sol = 0;
  for (int i = 1; i < (1 << factori.size()); ++i) {
    sol += m / fp[i];
  }
  return m - sol;
}

int main()
{
  ifstream in("frac.in");
  long long n, p;
  in >> n >> p;
  factorize(n);
  fp[0] = 1;
  for (int i = 0; i < factori.size(); ++i) {
    fp[1 << i] = factori[i];
  }
  for (int i = 1; i < (1 << factori.size()); ++i) {
    if ((i & (i - 1)) != 0) {
      fp[i] = fp[i & (i - 1)] * fp[i - (i & (i - 1))] * (-1);
    }
  }
  long long li = 1;
  long long lf = (1ll << 62);
  while (li < lf) {
    long long m = (li + lf) / 2;
    long long order = get_ord(m);
    //std::cerr << "li,lf,m,order: " << li << ", " << lf << ", " << m << ", " << order << std::endl;
    if (order < p) {
      li = m + 1;
    } else if (order > p) {
      lf = m - 1;
    } else {
      li = lf = m;
    }
  }

  while (relprime(li) == false) li--;

  ofstream out("frac.out");
  out << li << "\n";
  out.close();

  return 0;
}