#include <cstdio>
#include <cstdlib>
#include <cstring>
#define LL long long
using namespace std;
LL v[101],nr,bin[101];
LL pinex(LL k)
{
    memset(bin,0,sizeof bin);
    LL rez=0,i,j,par,semn,z;
    for(i=1; i<(1<<nr); i++)
    {
        j=1;
        while(bin[j]==1)
            bin[j++]=0;
        bin[j]=1;
        par=0;
        for(j=1; j<=nr; j++)
            par+=bin[j];
        if(par%2) semn=1;
        else semn=-1;
        z=1;
        for(j=1; j<=nr; j++)
            if(bin[j])
                z*=v[j];
        rez+=1LL*(k/z)*semn;
    }
    return k-rez;
}
int main()
{
    LL n,p,d,i,pas;
    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);
    scanf("%lld%lld",&n,&p);
    d=2LL;
    while(d*d<=n)
    {
        if(n%d==0)
        {
            v[++nr]=d;
            while(n%d==0)
                n/=d;
        }
        d++;
    }
    if(n-1)
        v[++nr]=n;
    i=0LL;
    pas=1LL*(1LL<<60LL);
    while(pas)
    {
        if(pas==16)
            d=1;
        if(pinex(i+pas)<p)
            i+=pas;
        pas/=2;
    }
    printf("%lld",i+1);

    return 0;
}