#include <cstdio>
#include <bitset>
#define ll long long
#define DIM 60

using namespace std;
int len, fact [DIM];

ll test (ll value)
{   
    int nr, j;
	ll p, i, sol = 0;
	for (i = 1; i < (1 << len); i++)
	{
		for (j = 0, p = 1, nr = 0; j < len; j++)
			if (i & (1 << j))
				++nr, p = 1LL * p * fact [j+1];
		if (nr & 1) nr = 1;
		else nr = -1;
		sol = sol + 1LL * nr * value / p;
	}
    return (value - sol);
}


void solve ()
{   
	ll st, dr, mij, res, sool = 0;
	int N, P;
	scanf ("%d%d\n", &N, &P);
	int i, val;
	val = N;
	for (i = 2; i * i <= val; i++)
	{
		if (val % i == 0) 
		{
			fact [++len] = i;
		    while (val % i == 0) val /= i;
		}
	}
	if (val != 1) fact [++len] = val;
	st = 1; 
	dr = (1LL << 62);
	while (st <= dr)
	{
		mij = (dr + st) >> 1 ;
		res = test (mij);
		if (res < P) st = mij + 1;
		else if (res > P) dr = mij - 1;
		else if (res == P) sool = mij, dr = mij - 1;
	}
	printf ("%lld\n", sool);
}

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