#include<fstream.h>
ifstream f("frac.in");
ofstream g("frac.out");
long n,a[100],p;

void factori(long x)
{long w=x,k=1;
	if(x%2==0)
	{while(x%2==0)
	    x/=2;
    a[k]=2;k++;
	}
	
		 for(int i=3;i<(w/2);i+=2)
		 {if(x%i==0)
			{while(x%i==0)
			   x/=i;
			    a[k]=i;k++;
			}
		 }
}
long calcul(long x)
{int i;
long pp=x,ppp=1;
for(i=1;i<=100&&a[i];i++)
	{
     ppp*=a[i];
	 pp-=x/ppp;
	}
return pp;

}
long int cautabin(long int in,long int sf)
{
long k=(in+sf)/2,t;
t=calcul(k);
if(t==p)
  return k;
if(t<p)
	in=k+1;
if(t>p)
sf=k-1;	
	  cautabin(in,sf);
if(in>sf)
return 0;

}
int main()

{

	f>>n>>p;
factori(n);
g<<cautabin(0,1000000000);
	
return 0;
}