#include <fstream>
#include <vector>

using namespace std;

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

typedef long long ll;

ll n,d;
vector<int>who;
int cnt=0;

ll val,ans;

void f(int strat,int add,ll prod) {
    if(strat==cnt)
        ans+=add*(val/prod);
    else {
        f(strat+1,add,prod);
        f(strat+1,add*-1,prod*who[strat]);
    }
}

int main() {
    fin>>n;
    for(d=2;d*d<=n;d++) {
        int cate=0;
        while(n%d==0) {
            n/=d;
            cate++;
        }
        if(cate)
            who.push_back(d);
    }
    if(n>1)
        who.push_back(n);
    cnt=who.size();
    ll r=0,pas=(1LL<<60);
    ll x;
    fin>>x;
    while(pas) {
        val=r+pas;
        ans=0;
        f(0,1,1);
        if(ans<x)
            r+=pas;
        pas/=2;
    }
    r++;
    fout<<r<<"\n";
    return 0;
}