#include<iostream>
#include<fstream>
#include<algorithm>
#include<set>
#include<cmath>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
#define ff(i,n) for (i = 1; i <= n; ++i)
#define dd(i) out << i <<'\n'
#define sq 110000
using namespace std;
int d[100000], ud;
long long N;
long long rez(long long x);
int main(){
    /*freopen ("geamuri.in", "r", stdin);
    freopen ("geamuri.out", "w", stdout);*/
    ifstream in("frac.in");
    ofstream out("frac.out");
	long long n, p, i, step, sol;
	in >> N >> p;
	n = N;
	for (i = 2; i <= sq; ++i) {
		if (!(n % i)) {
			d[++ud] = i;
			while (!(n % i)) {
				n /= i;
			}
		}
	}
	if (n > 1) d[++ud] = n;
	
	for (sol = 0, step = (1ll << 61); 
	sol <= (1ll << 61) && step; step >>= 1) {
		if (rez(sol + step) < p) {
			sol += step;
		}
	}
	dd(sol + 1);
}

long long rez(long long x) {
	long long mask = (1ll << ud) - 1, i, j, D, R = 0;
	int nrb;
	for (i = 1; i <= mask; ++i) {
		D = 1; nrb = 0;
		for (j = 0; j < ud; ++j) {
			if (i & (1ll << j)) {
				D *= d[j + 1];
				++nrb;
			}
		}
		if (nrb & 1) {
			R += (x / D);
		} else {
			R -= (x / D);
		}
	}
	return x - R;
}