#include<stdio.h>
#include<math.h>
#define tip long long
tip x,n,vect[60];
void desc(tip n);
tip cautare(tip);
tip determina(tip);

int main()
{tip d;
 freopen("frac.in","r",stdin);
 freopen("frac.out","w",stdout);
 scanf("%lld%lld",&n,&x);
 desc(n);
 d=cautare(x);
 printf("%lld",d);
 fclose(stdout);
  return 0;
  }

void desc(tip n)
{tip d;
 long double rad;
 for(d=2,rad=sqrt(n);d<=rad;d++)
	{if(!(n%d))
	  vect[++vect[0]]=d;
	while(!(n%d))
	  n/=d;
	 }
if(n>1)
 vect[++vect[0]]=n;
}


tip cautare(tip x)
{tip ld,ls=0,mij;
 ld=x*1000;
 while(ld>ls)
  {mij=(ld+ls)/2;
   if(determina(mij)>x)
	 ld=mij-1;
   else if(determina(mij)<x)
	  ls=mij+1;
	else
	   {while(determina(mij-1)==x)
		  mij--;
	   return mij; }
  }
 return mij;
 }
tip determina(tip d)
{tip j,i,d1=0,nr,p;
 for(i=1;i<1<<vect[0];i++)
   {
   for(j=0,p=1,nr=0;j<vect[0];j++)
	if(i&1<<j)
	  {nr++;p*=vect[j+1];
	   }
   if(nr%2)
	 d1+=d/p;
   else
	 d1-=d/p;
   }
 return d-d1;

 }