#include<stdio.h>
int factor[100], nf, sub[100];
long long n,p,nrf;
void desc(long long n)
{
	if(n%2==0) factor[nf++]=2;
	while(n%2==0)  n/=2;
	long long d=3;
	while(n>1)
	{
		if(n%d==0) factor[nf++]=d;
		while(n%d==0)  n/=d;
		d+=2;
	}
}
long long cmmdc(long long a, long long b)

{
	long long r;
	while(r=a%b)
	{
		a=b;
		b=r;
	}
	return b;
}
void calcul(int s,long long m)
{
	long p=1;
	for(int i=0;i<nf;i++)
		if(sub[i]) p*=factor[i];
	if(s%2) nrf+=m/p;
		else nrf-=m/p;
}	
void subm(int k,int s,long long m)
{
	int i;
	if(k==nf)
	{
		if(s) calcul(s,m);
		return;
	}
	for(i=0;i<=1;i++)
	{
		sub[k]=i;
		s+=i;
		subm(k+1,s,m);
		s-=i;
	}
}
long long caut(long long li, long long ls)
{
	long long m;
	while(li<=ls)
	{
		m=(li+ls)/2;
		nrf=0;
		subm(0,0,m);
		if(p==m-nrf) return m;
		else if(p<m-nrf) ls=m-1;
		       else li=m+1;
	}
	nrf=0;
	subm(0,0,ls);
	if(ls-nrf==p) return ls;
	 else return ls+1;
}	
int main()
{
	freopen("frac.in", "rt", stdin);
	
	freopen("frac.out", "wt", stdout);
	scanf("%lld%lld", &n,&p);
	desc(n);
	long long x=1;
	x=x<<62;
	long long rez=caut(0,x);
	while(cmmdc(rez,n)!=1) rez--;
	if(rez==0) rez=1;
	printf("%lld\n", rez);
	return 0;
}