#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll nmax = 110000;
const int pmax = 61;

int prime[nmax+5];
int primeNr;

int fct[nmax+5];
int fctNr;

bool c[nmax+5];
void sieve() {
	for(int i=3; i*i<=nmax; i+=2)
		if(!c[i])
			for(int j=i*i; j<=nmax; j+=i)
				c[i] = true;
	prime[++primeNr] = 2;
	for(int i=3; i<=nmax; i+=2) if(!c[i]) prime[++primeNr] = i;
}

ll nr(ll x) {
	ll sum = 0;
	for(ll i=1; i<(1<<fctNr); i++) {
		ll temp = i;
		int w = -1;
		ll prod = 1;
		int ind = 1;
		while(temp) {
			if(temp&1) w = -w, prod *= fct[ind];
			temp = temp >> 1;
			ind++;
		}
		sum = sum + w * (x / prod);
	}
	return x - sum;
}

int main() {
	ifstream f("frac.in");
	ofstream g("frac.out");

	ll n,p; f >> n >> p;
	sieve();
	int k = 1;
	while(prime[k]*prime[k]<=n and k<=primeNr) {
		if(n%prime[k]==0) fct[++fctNr] = prime[k];
		while(n%prime[k]==0) n /= prime[k];
		k++;
	}
	if(n!=1) fct[++fctNr] = n;

	ll ans = 0;
	for(int i=pmax; i>=0; i--)
		if(nr(ans+(1LL<<i))<p) ans += (1LL<<i);
	g << ans+1;
	return 0;
}