#include <iostream>
#include <fstream>
#define ll long long
using namespace std;
ifstream si("frac.in");
ofstream so("frac.out");
ll d[25];
int nd;
ll intr(ll x)
{
    ll i,j,prod,sol=x,lim=1<<nd;
    for(i=1;i<lim;++i)
    {
        prod=1;
        for(j=0;j<nd;++j)
        {
            if(i&(1<<j))
                prod*=-d[j+1];
        }
        sol+=x/prod;
    }
    return sol;
}
int main()
{
    ll n,x;
    si>>n>>x;
    ll r=n;
    ll i;
    for(i=2;i*i<=n;i++)
        if(n%i==0)
        {
            d[++nd] = i;
            while(n%i==0)
                n/=i;
        }
    if(n!=1)
        d[++nd]=n;
    n=r;
    ll sol,st=1,dr=1LL<<61,mij;
    while(st<=dr)
    {
        mij=(st+dr)>>1;
        if(intr(mij)<x)
        {
            st=mij+1;
        }
        else
        {
            sol=mij;
            dr=mij-1;
        }
    }
    so<<sol;
    return 0;
}