#include <stdio.h>

#define MAX_PRIMES 20
#define START_STEP (1ULL << 61)

typedef unsigned long long ull;

ull factors[MAX_PRIMES];
int cntFactors;

static inline void breakFactors(ull n) {
  cntFactors = 0;

  if (!(n & 1)) {
    factors[cntFactors++] = 2;
    n /= (n & -n);
  }
  for (ull i = 3; i * i <= n; i += 2) {
    ull q = n / i;
    if (!(n - q * i)) {
      factors[cntFactors++] = i;
      do {
        n = q;
        q = n / i;
      } while (!(n - q * i));
    }
  }
  if (n != 1) {
    factors[cntFactors++] = n;
  }
}

static inline ull cntPinex(ull A) {
  ull q = A;

  for (int i = (1 << cntFactors) - 1; i > 0; i--) {
    ull prod = 1;
    int cnt = 0;
    for (int j = 0; j < cntFactors; j++) {
      if (i & (1 << j)) {
        cnt++;
        prod *= factors[j];
      }
    }
    if (cnt & 1) {
      q -= A / prod;
    } else {
      q += A / prod;
    }
  }
  return q;
}

int main(void) {
  FILE *f = fopen("frac.in", "r");
  ull n, p;
  ull q, step;

  fscanf(f, "%llu%llu", &n, &p);
  fclose(f);

  breakFactors(n);

  q = START_STEP;
  step = START_STEP >> 1;
  do {
    if (cntPinex(q - step) >= p) {
      q -= step;
    }
    step >>= 1ULL;
  } while (step);

  f = fopen("frac.out", "w");
  fprintf(f, "%llu\n", q);
  fclose(f);
  return 0;
}