#include <bits/stdc++.h>
#define NMAX 100005
#define MOD 666013
#define INF 0x3f3f3f3f
#define x first
#define y second

using namespace std;

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

vector<long long> diviz;

bool sedivide(long long x) {
	for(auto it:diviz)
		if(x%it==0) return 1;

	return 0;
}

int main() {
	long long st,dr,mid,n,p,aux,d,i;
	double smaller;

	fin>>n>>p;
	aux=n;

	d=2;
	while(d*d<=n) {
		if(n%d==0) {
			diviz.push_back(d);

			while(n%d==0)
				n/=d;
		}

		++d;
	}

	if(n!=1) diviz.push_back(n);

	st=1;
	dr=(1LL<<61);
	while(st<=dr) {
		mid=(st+dr)/2;

		smaller=mid;
		for(auto it:diviz) {
			smaller/=it;
			smaller*=(it-1);
		}

		if(smaller<=p-1) st=mid+1;
		else dr=mid-1;
	}

	while(sedivide(st)) ++st;

	smaller=st;
	for(auto it:diviz) {
		smaller/=it;
		smaller*=(it-1);
	}

	if(smaller>p) {
		st--;
		while(sedivide(st))
			--st;
	}

	fout<<st;

	return 0;
}