#include <vector>
#include <fstream>

using namespace std;

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

long long n,p;
vector < long long  > D;
long long PINEX(long long x);
long long Binary_Search();

int main() {

	fin >> n >> p;
	int nr = 0;
	while ( n % 2 == 0)
		++nr , n /= 2;
	if ( nr )
		D.push_back(2);
	for ( long long d = 3; d * d <= n; d += 2) {
		nr = 0;
		while ( n % d == 0)
			++nr, n /= d;
		if ( nr )
			D.push_back(d);
	}
	if ( n > 1 )
			D.push_back(n);

    fout << Binary_Search();
}


long long Binary_Search() {
	long long st = 1, dr = 1LL << 60, rez,mj;
	while ( st <= dr ) {
		mj = ( st + dr ) / 2;
		if ( PINEX(mj) == p ) {
			rez = mj;
			dr = mj - 1;
			}
		else
		if (PINEX(mj) < p )
			st = mj + 1;
		else
			dr = mj - 1;
	}
	return rez;
}

long long PINEX(long long x) {

	long long sol = 0,mult,card;
	for ( int mask = 1; mask < ( 1 << D.size() ); ++mask) {
		mult = 1;
		card = 0;
		int cnt = 0;
		for ( const long long & j : D ) {
			if ( mask & ( 1 << cnt) ) {
				mult *= j;
				++card;
				}
			++cnt;
			}
		if ( card & 1 )
			sol += x / mult;
		else
			sol -= x / mult;
		}
	return x - sol;
}