#include<fstream.h>
#include<math.h>
ifstream f("frac.in");
ofstream g("frac.out");
unsigned long n,p,x;
#define max 50
int a[max],z;
unsigned long long in=1,sf=2305843009213693952, mij,t;

void descompune(unsigned long q)
{int i;
for(i=2;i<=sqrt(q);i++)
   if(q%i==0){a[z]=i;z++;
	      while(q%i==0)
			q/=i;	
		}

}

long long calcul(long long x)
{int i;
long long k=1;
for(i=0;i<=z;i++)
   {k*=a[i];x-=x/k;}
return x;}
void binara()
{
 mij=(in+sf)/2;
t=calcul(mij);
 if(t>p)
      {sf=mij;binara();}
 else if(t<p)
        {in=mij;binara();}
       else g<<mij;
}
int main()
{
f>>n>>p;
descompune(n);
binara();
return 0;
}