#include <fstream>
#include <vector>
#define ll long long

ll n, p;
std::vector<ll>v;

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

bool check(ll k) {
	ll ans = k;
	for(ll msk=1;msk<(1LL<<(int)v.size());msk++) {
		ll nr = __builtin_popcount(msk), p = 1;
		for(int bit = 0; bit<v.size(); bit++) if(msk&(1LL<<bit)) p *= v[bit];
		ans += ((nr%2==0)?(k/p):(-(k/p)));
	}
	return (ans<p);
}

void solve() {
	ll st = 1, dr = (1LL<<61)-1;
	while(st<=dr) {
		ll mij = (st+dr)>>1;
		if(check(mij)) st = mij + 1;
		else dr = mij - 1;
	}
	fout<<st;
}

int main() {
	fin>>n>>p;
	for(int i=2;i*i<=n;i++) if(!(n%i)){
		v.push_back(i);	
		while(!(n%i)) n/=i;
	}
	if(n!=1) v.push_back(n);
	solve();
}