#include <cstdio>
#include <cstring>

using namespace std;

long long n, i, j, p, m, f[20], nr, q, l, sol, ad;

int v[20];


void desc(long long n) {

	int d=3;
	
	if ( n%2 == 0 ) {
		nr=1; f[1]=2;
		while ( n%2 == 0 )
			n/=2;
	}

	while (n>1) {
		while ( (n%d) && (d*d <= n) )
			d++;

		if (d*d>n) {
			nr++; f[nr]=n;
			break;
		}
		nr++;
		f[nr] = d;

		while ( n%d == 0 )
			n/=d;
	}

}


long long phi(long long n) {
	long i;
	long double t;
	long long rez;

	t=n;
	for (i=1; i<=nr; i++) 
		t = t * (1 - 1.0/f[i]);

	rez= (long) t;
//	printf("%lld\n", rez);
	return rez+1;
}

long long boom(long long x) {
	int i, p, s, j, rez=0;

	memset(v, 0, sizeof(v));
	v[nr]=1;

	if (x == 1)
		return 1;

	for (i=1; i< (1<<nr); i++) {
		s=0;p=1;

		for (j=1; j<=nr; j++) {
			s+=v[j];
			if (v[j] == 1)
				p=p*f[j];
		}

		if (s%2==0)
			rez-= (x/p);
		else
			rez+= (x/p);

//		printf("%d %d %d\n", s, p, rez);

		j=nr;
		while (v[j] == 1) {
			v[j]=0;
			j--;
		}
		v[j]=1;

	}

	return x-rez;

}

void bsearch(long long l, long long r) {
	long long m = (l+r) / 2, rez;

	rez = boom(m); 

	if (l>=r)
		return;
	
	if ( (rez == q) && ( boom(m-1) < q ) ) {
		sol=m;
		return;
	}

	if ( rez < q )
		bsearch(m+1, r);
	else
		bsearch(l, m-1);
}


int main() {
	freopen("frac.in", "r", stdin);
	freopen("frac.out", "w", stdout);

	scanf("%lld%lld", &n, &p);

	desc(n);
	m = phi(n);

	ad = (p-1) / m;

	q = (p%m);

	if ( q == 0 )
		q=m;

/*	l= 1 << 30;
	l = l << 30;
	l = l << 1;*/

	l=12;

	bsearch(1, l);

//	printf("%d\n", boom(12));

	printf("%lld\n", sol + ad * n);

	return 0;
}