#include <iostream>
#include <fstream>

using namespace std;

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

long long n, p;
long long div[20];
int cnt;

void desc() {
  for(long long i = 2; i * i <= n; i++) {
    if(n % i == 0) {
      div[cnt++] = i;
      while(n % i == 0)
        n /= i;
    }
  }

  if(1 < n)
    div[cnt++] = n;
}

long long convert(long long no) {
  long long r = 0, a, b;
  for(long long i = 0; i < (1LL << cnt); i++) {
    a = b = 1;
    for(long long j = 0; j <= cnt; j++) {
      if((i & (1 << j)) != 0) {
        a *= div[j];
        b *= -1;
      }
    }
    r += b * no / a;
  }
  return r;
}

long long binsrc() {
  long long pas = 1LL << 60;
  long long r = 0;
  while(pas != 0) {
    if(convert(r + pas) < p)
      r += pas;
    pas /= 2;
  }
  return ++r;
}

int main()
{
  in >> n >> p;
  desc();
  out << binsrc() << '\n';
  in.close();
  out.close();
  return 0;
}