#include <bits/stdc++.h>
/// Template Dutzu
#define fast ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;

ifstream fin("frac.in");
ofstream fout("frac.out");
long long n;
int b[10001];
int d[10001];
void bkt(int cnt,long long a,long long& neprim)
{
    if (cnt>d[0])
    {
        long long aux=1;
        int lg=0;
        for (int i=1;i<=d[0];i++)
            if (b[i])
            {
                aux*=d[i];
                lg++;
            }
        if (lg==0)
            return;
           /// cout<<neprim<<' '<<aux<<' '<<lg<<'\n';
        if (lg%2)
            neprim+=a/aux;
        else
            neprim-=a/aux;
            return;
    }

            bkt(cnt+1,a,neprim);
            b[cnt]=1;
            bkt(cnt+1,a,neprim);
            b[cnt]=0;
}
long long pr(long long a)
{

    long long neprim=0;
        bkt(1,a,neprim);
    cout<<a-neprim<<' ';
    return a-neprim;

}
int main()
{
    fast
    long long p;
    fin>>n>>p;
    long long aux=n;
    for (int i=2;i*i<=aux;i++)
    {
        if (aux%i==0)
            d[++d[0]]=i;
        while (aux%i==0)
            aux/=i;
    }
    if (aux)
        d[++d[0]]=aux;
    long long st=1,dr=20,mij,rez=0;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (pr(mij)>=p)
        {
            rez=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    fout<<rez;
    return 0;
}