#include<bits/stdc++.h>

using namespace std;

int_fast64_t n,p;

vector <int_fast64_t> v;

void divv(int_fast64_t x)
{
    int_fast64_t d=2;
    if(x%d==0)
    {
        while(x%d==0)
        {
            x/=d;
        }
        v.push_back(d);
    }
    d=3;
    while(d*d<=x && x>1)
    {
        if(x%d==0)
        {
            while(x% d==0)
            {
                x/=d;
            }
            v.push_back(d);
        }
        d+=2;
    }
    if(x>1) v.push_back(x);
}

int_fast64_t pinex(int_fast64_t x)
{
    int_fast64_t ans,maxim;
    ans=0;
    maxim=1LL<<v.size();
    for(int i=1; i<maxim; ++i)
    {
        int_fast64_t prod=1;
        int_fast64_t nr=0;
        for(int j=0; j<v.size(); ++j)
        {
            if(i & (1LL<<j))
            {
                nr++;
                prod*=v[j];
            }
            if(nr%2==1)
            {
                ans+=x/prod;
            }
            else
            {
                ans-=x/prod;
            }
        }
    }
    return (x-ans>=p);
}
int main()
{
    ifstream fin("frac.in");
    ofstream fout("frac.out");
    fin>>n>>p;
    divv(n);
    int_fast64_t st=1,dr=(1LL<<62),last=1;
    while(st<=dr)
    {
        int_fast64_t mij=(st+dr)/2;
        if(pinex(mij))
        {
            dr=mij-1;
            last=mij;
        }
        else
        {
            st=mij+1;
        }
    }
    fout<<last;
    return 0;
}