#include <bits/stdc++.h>
#define int long long
using namespace std;
int d,t;
bool prim[1000005];
int fprim[80000];
int fact[100];
void sieve() {

	for (int i = 2; i < 1000000; i++)
		if (!prim[i]) {
			for (int j = 2 * i; j < 1000000; j += i)
				prim[j] = 1;
			fprim[++fprim[0]] = i;
		}
}
void desc (int b)
{
  d=0,t=0;
  while (b > 1)
  {
    d++;
    if (b % fprim[d] == 0)
    {
      fact[++t] = fprim[d];
      while (b % fprim[d] == 0)
        b /= fprim[d];
    }

    if (fprim[d] > sqrt(b) && b > 1)
    {
      fact[++t] = b;
      b = 1;
    }
  }
}
int calc(int a, int b)
{
  desc(b);
  int sol = a;
  for (int i = 1; i < (1 << t); i++)
  {
    int nr = 0, prod = 1;
     for (int j = 0; j < t; j++)
      if ((1 << j) & i)
      {
        prod = prod * fact[j + 1];
        nr++;
      }

    if (nr % 2)
      nr = -1;
    else
      nr = 1;

    sol = sol + nr * a / prod;
  }
  return sol;
}
int32_t main()
{
  freopen("frac.in","r",stdin);
  freopen("frac.out","w",stdout);
  sieve();
  int n,trebe,ans=0;
  scanf("%lld %lld",&n,&trebe);
  int st=1,dr=(1<<61);
  while(st<=dr)
  {
      int mid=(st+dr)/2;
      if(calc(mid,n)>trebe)
      {
          dr=mid-1;
      }
      else
      if(calc(mid,n)<trebe)
      {
          st=mid+1;
      }
      else
        {
            calc(mid,n);
            ans=mid;
            dr=mid-1;
        }
  }
  printf("%lld\n",ans);
  return 0;
}