#include <bits/stdc++.h>
#define lli long long int
#define ull unsigned long long
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
unsigned long long int a, b, c;

vector <lli> factoria;

void divprim(long long x)
{
    factoria.clear();
    for(lli i=2; i*i<=x; i++)
    {
        if(x%i==0)
        {
            factoria.push_back(i);
            while(x%i==0)
            {
                x/=i;
            }
        }
    }
    if(x>1)
    {
        factoria.push_back(x);
    }
}

void back(int index, ull dc, int poz,ull urm)
{
    if(index>0)
    {
        if(index%2==0)
        {
            c=c-urm/dc;
        }
        else
        {
            c=c+urm/dc;
        }
    }
    for(int i=poz+1; i<factoria.size(); i++)
    {
        dc=dc*factoria[i];
        back(index+1, dc, i, urm);
        dc/=factoria[i];
    }
}

int main()
{
    fin>>a>>b;
    divprim(a);
   ull st=1, dr=LLONG_MAX;
    while(st<=dr)
    {
        ull mid = (st + dr) / 2;
        c = 0;
        back(0, 1, -1, mid);
        ull nr = mid - c;
        if (nr < b)
        {
            st=mid+1;
        }
        else
        {
            dr=mid-1;
        }
    }
    fout<<st;

}