#include <stdio.h>

const char iname[] = "frac.in";
const char oname[] = "frac.out";

typedef long long i64;


i64 L[64];

int nrdiv;

void descomp(i64 n)
{
	if ((n & 1) == 0) {
		while ((n & 1) == 0)
			n >>= 1;
		L[nrdiv ++] = 2;
	}
	for (i64 i = 3; i * i <= n; i += 2) {
		if ((n % i) == 0) {
			while ((n % i) == 0)
				n /= i;
			L[nrdiv ++] = i;
		}
	}
	if (n > 1)
		L[nrdiv ++] = n;
}

i64 f(i64 delta, i64 n)
{
	i64 ans = 0;

	for (int stp = 1; stp < 1 << nrdiv; ++ stp) {
		i64 prod = 1;
		int cnt = 0;
		for (int i = 0; i < nrdiv; ++ i) {
			if ((stp >> i) & 1) {
				cnt ++;
				prod *= L[i];
			}
		}
		i64 sgn = (cnt & 1) ? (+1) : (-1);
		ans += sgn * (delta / prod);
	}
	return ans;
}

int main(void)
{
	i64 n, p;

	FILE *fi = fopen(iname, "r");

	fscanf(fi, "%lld %lld", &n, &p);
	fclose(fi);

	descomp(n);

	i64 delta = 3 * (1e18);
	i64 i, stp;
	for (stp = 1; stp < delta; stp <<= 1) ;
	for (i = 1; stp; stp >>= 1) {
		if ((i + stp <= delta) && ((i + stp) - f(i + stp, n) < p))
			i += stp;
	}
	if (i - f(i, n) < p)
		i ++;

	FILE *fo = fopen(oname, "w");

	fprintf(fo, "%lld\n", i);
	fclose(fo);

	return 0;
}