/**#include<fstream>
#define LL long long
using namespace std;
ifstream f("frac.in"); ofstream g("frac.out");
LL p,n,k,prim[11];
LL nr(LL x)
{   LL r=0;
    for(LL prod,sgn,i=0;i<(1LL<<k);++i)
    {   prod=sgn=1;
        for(LL j=0;j<k;++j)
			if((i&(1<<j)) != 0) prod*=prim[j], sgn*=-1;
		r+=sgn*x/prod;
    }
    return r;
}
LL caut()
{   LL i,pas=1LL<<60;
    for(i=0;pas;pas>>=1)
        if(nr(i+pas)<p) i+=pas;
    return i+1;
}
int main()
{   f>>n>>p;
    for(LL i=2;i*i<=n;++i)
        if (n%i==0)
        {   prim[k++]=i;
            while(n%i==0) n/=i;
        }
    if(n>1) prim[k++]=n;
    g<<caut()<<'\n'; g.close(); return 0;
}
*/
#include <iostream>
#include <fstream>
#define ull unsigned long long
using namespace std;
ifstream f("frac.in"); ofstream g("frac.out");
ull k,prim[11];
ull rez(ull x)
{   ull nr=x;
    for(int i=1;i<(1LL<<k);i++)
    {   ull q=0,p=1;
        for(ull j=0;j<k;j++)
            if(i&(1LL<<j)) {q++; p=p*prim[j+1];}
        if(q%2)nr-=x/p; else nr+=x/p;
    }
    return nr;
}
int main()
{   ull n,p;
    f>>n>>p;
    ull d=2;
    while(d*d<=n)
    {   if(n%d==0)
        {   prim[++k]=d;
            while(n%d==0) n/=d;
        }
        d++;
    }
    if(n>1)prim[++k]=n;
    ull st=1,dr=(1LL<<61);
    while(st<=dr)
    {   ull m=(st+dr)/2;
        if(rez(m)<p) st=m+1; else dr=m-1;
    }
    g<<st; g.close(); f.close(); return 0;
}
/*
#include <iostream>
#include <fstream>
#define ull unsigned long long

using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
ull v[2000002],k=0;

ull rez(ull x)
{
    ull nr=x,q,p;
    for(int i=1;i<(1LL<<k);i++)
    {
        q=0;
        p=1;
        for(int j=0;j<k;j++)
        {
            if(i&(1LL<<j))
            {
                q++;
                p=p*v[j+1];
            }
        }
        if(q%2==1)nr=nr-x/p;
        else nr=nr+x/p;
    }
    return nr;
}

int main()
{
    ull n,p;
    fin>>n>>p;
    if(n%2==0)
    {
        v[1]=2;
        k=1;
        while(n%2==0)n/=2;
    }
    ull d=3;
    while(n>1&&d*d<=n)
    {
        if(n%d==0)
        {
            v[++k]=d;
            while(n%d==0)n/=d;
        }
        d+=2;
    }
    if(n>1)v[++k]=n;

    ull st=1,dr=(1LL<<61);
    while(st<=dr)
    {
        ull m=(st+dr)/2;
        if(rez(m)<p)st=m+1;
        else dr=m-1;
    }
    fout<<st;
}

*/