#include <fstream>
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
long long k, p;
long long v[101], di[101];

long long sol(long long n)
{
    long long nr=0, i;
    for(i=0;i<=k;i++)
    {
        v[i]=0;
    }
    while(!v[0])
    {
        i=1LL*k;
        while(v[i]==1)
        {
            v[i]=0;
            i--;
        }
        v[i]=1;
        long long prod=1, x=0;
        for(i=1;i<=k;i++)
        {
            if(v[i]==1)
            {
                prod*=di[i];
                x++;
            }
        }
        if(prod!=1)
        {
            if(x%2==1)
            {
                nr+=n/prod;
            }
            else
            {
                nr-=n/prod;
            }
        }
    }
    if(nr>0)
    {
        n-=nr;
    }
    else
    {
        n+=nr;
    }
    if(n>=p)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

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