#include <bits/stdc++.h>
///N=12*10^9
///P=10^14
///Sol=2^61
using namespace std;
typedef long long ll;
///
ll n, p, r, l, i, j, k, total, ret;
bitset<300001> ciur;
vector<ll> primelist, divlist;
///
void read();
void solve();
void write();
ll pinex(ll a);
void buildCiur();
bool check(ll val);
int main()
{
    read();
    solve();
    write();
    return 0;
}
void read(){
    freopen("frac.in", "r", stdin);
    scanf("%lld%lld", &n, &p);
    fclose(stdin);
}
void solve(){
    l=r=1LL; for(i=1; i<=61; ++i) r*=2;
    buildCiur();
    for(auto i:primelist){
        if(1LL*i*i>n) break;
        if(!(n%i)){
            divlist.push_back(i); ++total;
            while(!(n%i)) n/=i;
        }
    }
    if(n>1) {divlist.push_back(n); ++total;}
    while(l<=r){
        ll m=(l+r)/2;
        ll pn=pinex(m);
        if(pn==p){ret=m; break;}
        else if(pn>p) r=m-1;
        else l=m+1;
    }
    while(!check(ret)) --ret;
}
void write(){
    freopen("frac.out", "w", stdout);
    printf("%lld", ret);
    fclose(stdout);
}
ll pinex(ll a){
    ll sol=0LL, div;
    int mp;
    for(i=1; i<(1<<total); ++i){
        ll c=i; div=1LL; mp=0;
        for(j=0; j<total; ++j){
            if(c&1){
                mp^=1;
                div*=divlist[j];
            }
            c>>=1;
        }
        sol+=(a/div);
        if(!mp) sol-=2*(a/div);
    }
    return a-sol;
}
void buildCiur(){
    for(i=2; i<=300000; ++i){
        if(ciur[i]) continue;
        primelist.push_back(i);
        for(j=2*i; j<=300000; j+=i) ciur[j]=true;
    }
}
bool check(ll val){
    for(auto i:divlist) if(!(val%i)) return false;
    return true;
}