/*
Keep It Simple!
*/

#include <fstream>
#include <iostream>
#include <cmath>

#define Upper_Bound 1000000
#define ll long long

using namespace std;

ifstream fin("frac.in");
ofstream fout("frac.out");

const int Max_PrimeC = 90000;
const ll Max_N = 12000000005;

ll T, A, B, P, factors[30];
int p_count, primes[Max_PrimeC], f_count;
bool seen[Upper_Bound];

void GeneratePrimes()
{
	primes[++p_count] = 2;
	for (int i = 3; i <= Upper_Bound; i += 2)
	{
		if (!seen[i])
		{
			primes[++p_count] = i;
			for (int j = i + i; j <= Upper_Bound; j += i)
				seen[j] = 1;
		}
	}
}

void ComputeFactors(ll B)
{
	int idx = 1;
	int aux = B;
	while (B != 1)
	{
		if (!(B%primes[idx])) factors[++f_count] = primes[idx];
		while (!(B%primes[idx])) B /= primes[idx];
		idx++;

		if (primes[idx] > sqrt(B) && B > 1)
		{
			factors[++f_count] = B;
			B = 1;
		}
	}
	B = aux;
}

ll pinex(ll A, ll B)
{
	ll solution = A;

	for (int i = 1; i < (1 << f_count); ++i)
	{
		int sign = 0;
		ll prod = 1;
		for (int j = 0; j < f_count; j++)
			if ((1 << j) & i)
			{
			prod = 1LL * factors[j + 1] * prod;
			sign++;
			}

		if (sign % 2) sign = -1;
		else sign = 1;

		solution = solution + 1LL * sign * A / prod;
	}
	return solution;
}

bool IsPrime(ll x)
{
	if (x % 2 == 0)
		return 0;
	if (x < Upper_Bound)
		return !seen[x];
	else
	{
		for (int i = 1; i <= p_count; ++i)
			if (x%primes[i] == 0)
				return 0;
	}
	return 1;
}

ll FirstPrimeDown(ll left, ll right)
{
	for (ll i = right; i >= left; i--)
		if (IsPrime(i))
			return i;
	return -1;
}

ll GCD(ll u, ll v) {
	while (v != 0) {
		ll r = u % v;
		u = v;
		v = r;
	}
	return u;
}

void Binary_Search_Prime(ll P)
{
	ll left = 0, right = 1LL << 60;

	while (right)
	{
		if (pinex(left + right, B) < P)
			left += right;
		right >>= 1;
	}

	fout << left + 1;
}

void Solve()
{
	fin >> B >> P;
	GeneratePrimes();

	f_count = 0;
	ComputeFactors(B);

	//Binary Search for solution
	Binary_Search_Prime(P);


}

int main()
{
	Solve();
	return 0;
}