#include <iostream>
#include <fstream>

using namespace std;
typedef long long ll;

ll n,p,st,dr,mij,ans,pr;
int sz,nrp;
ll np[30];
bool pa[30];
ll gcd(ll a,ll b){
  ll r;
  do{
    r=a%b;
    a=b;
    b=r;
  }while(r);
  return a;
}
ll rez(ll a,ll b){
  sz=0;
  for(ll i=2;i*i<=b;i++)
    if(b%i==0){
      np[++sz]=i;
      while(b%i==0)b/=i;
    }
  if(b!=1)np[++sz]=b;
  ans=0;
  for(int nrd=1;nrd<(1<<sz);nrd++){
    nrp=0;
    for(int bt=1,bi=1;bi<=sz;bt<<=1,bi++)
      pa[bi]=((nrd|bt)==nrd),
      nrp+=((nrd|bt)==nrd);
    pr=1;
    for(int i=1;i<=sz;i++)pr*=(pa[i])?np[i]:1;
    if(nrp%2)ans+=a/pr; else ans-=a/pr;
  }
  return a-ans;
}

int main()
{
    ifstream f ("frac.in");
    ofstream g ("frac.out");
    f>>n>>p;
    st=1,dr=1LL<<61;
    while(st<dr){
      mij=(st+dr+1)/2;
      if(rez(mij,n)<=p)st=mij;
      else dr=mij-1;
    }
    while(gcd(st,n)!=1)st--;
    g<<st;
    f.close ();
    g.close ();
    return 0;
}