#include<stdio.h>
#include<math.h>
#define LL long long
LL fact[69];

void desc(LL n)
{
    LL d=2,lim=sqrt(n);
    while(n>1 && d<=lim)
    {
        if(n%d==0)
        {
            fact[++fact[0]]=d;
            while(n%d==0)
                n/=d;
        }
        d++;
    }
if(n>1)
    fact[++fact[0]]=n;
}

LL prod[(LL)1<<20];

LL nr(LL x)
{
    int i;
    LL sol=0;
    for(i=1;i<=prod[0];i++)
        sol+=x/prod[i];
    return x-sol;
}

int main()
{
    LL i,n,p,st,dr,m,num,j,sol=-1;

    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);

    scanf("%lld%lld",&n,&p);
    desc(n);
    for(i=1;i<(LL)1<<fact[0];i++)
    {
        prod[0]++; prod[prod[0]]=1;
        for(j=0;j<fact[0];j++)
            if(i&((LL)1<<j))
                prod[prod[0]]=prod[prod[0]]*fact[j+1]*(-1);
        prod[prod[0]]*=(-1);
    }
    st=1,dr=(LL)1<<61;
    while(st<=dr)
    {
        m=(st+dr)>>1;
        num=nr(m);
        if(num>p)
            dr=m-1;
        if(num<p)
            st=m+1;
        if(num==p)
            sol=m,dr=m-1;
    }

    printf("%lld",sol);
    return 0;
}