#include <fstream>
#define ll long long
#include <vector>
#include <climits>
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
ll n,p;
ll st,dr;
ll all;
vector<ll>a;
bool check(ll val)
{
    ll ans=val;
    for(int i=1;i<all;i++)
    {
        int bits=0;
        ll r=1;
        for(int j=0;j<a.size();j++)
            if((1<<j)&i)
            {
                bits++;
                r*=a[j];
            }
        if(bits%2)
            ans-=(val/r);
        else
            ans+=(val/r);
    }
    return ans<p;
}
int main()
{
    st=1;
    dr=LONG_MAX;
    f>>n>>p;
    if(n%2==0)
        a.push_back(2);
    while(n%2==0)
        n/=2;
    ll d=3;
    while(d*d<=n)
    {
        if(n%d==0)
            a.push_back(d);
        while(n%d==0)
            n/=d;
        d+=2;
    }
    if(n!=1)
        a.push_back(n);
    all=1<<a.size();
    while(st<=dr)
    {
        ll mj=(st+dr)/2;
        if(check(mj))
            st=mj+1;
        else
            dr=mj-1;
    }
    g<<st;
    return 0;
}