#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
long long n,p,k,st,dr,mid,v[101];
bool f[101];

bool calc(long long x) {
    memset(f,0,sizeof(f));
    long long sol=0;
    while (f[0]==0) {
        int i=k;
        while (f[i]==1)
            f[i--]=0;
        f[i]=1;
        long long p=1;
        long long nr=0;
        for (int i=1;i<=k;i++)
            if (f[i]==1) {
                p*=v[i];
                nr++;
            }
        if (p!=1) {
            if (nr%2==0)
                sol-=x/p;
            else
                sol+=x/p;
        }
    }
    if (sol>0)
        x-=sol;
    else
        x+=sol;
    return x<p;
}

int main() {
    fin>>n>>p;
    for (long long d=2;n!=1 && d*d<=n;d++)
        if (n%d==0) {
            v[++k]=d;
            while (n%d==0)
                n/=d;
        }
    if (n!=1)
        v[++k]=n;
    st=1;
    dr=(1LL<<61);
    while (st<=dr) {
        mid=(st+dr)/2;
        if (calc(mid))
            st=mid+1;
        else
            dr=mid-1;
    }
    fout<<st;
    return 0;
}