#include <fstream>
#include <bitset>
//generare pe biti toate submultimile
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
long long divi[60],N,P,i,k,last,st,dr,mij;
long long pinex(long long A)
{
    long long factor,i,rez=0,submultimi=(1LL<<divi[0]),semn;
    for(i=1;i<submultimi;i++)
    {
        factor=1;semn=0;;
        for(int j=0;j<divi[0];j++)
        {
            if( (i & (1<<j)) !=0)
            {
                factor*=divi[j+1];
                semn++;
            }
        }
        if(semn%2==1) rez+=A/factor;
        else rez-=A/factor;
    }
    return A-rez;
}
int main()
{
    fin>>N>>P;
    for(i=2;i*i<=N;i++)
    {
        if(N%i==0) divi[++divi[0]]=i;
        while(N%i==0) N/=i;
    }
    if(N>1) divi[++divi[0]]=N;
    st=0,dr=(1LL<<61);
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(pinex(mij)>=P)
        {
            last=mij;
            dr=mij-1;
        }
        else st=mij+1;
    }
    fout<<last;
}