#include <iostream>
#include <fstream>
using namespace std;
ifstream f("frac.in");
ofstream g("frac.out");
long long n,p,st,dr,i,j,divizori[5005],nr;
void descompunere(long long n)
{
    if (n%2==0)
        divizori[++nr]=2;
    while (n%2==0)
        n/=2;
    i=3;
    while (n>1)
    {
        if (n%i==0)
        {
            divizori[++nr]=i;
            while (n%i==0&&n>1)
                n/=i;
        }
        i+=2;
    }
}
long long ans(long long m)
{
    long long rez=m;
    long long pow=(1<<nr)-1;
    for (i=1; i<=pow; i++)
    {
        int nrbiti=0;
        long long aux=m;
        for (j=1; j<=nr; j++)
        {
            if ((1<<(j-1)&i)>0)
                aux/=divizori[j],nrbiti++;
        }
        if (nrbiti%2==1)
            rez-=aux;
        else
            rez+=aux;
    }
    return rez;
}

int main()
{
    f>> n >> p;
    descompunere(n);
    st=1;
    dr=9000000000000000005;
    while(st<dr)
    {
        long long m=(st+dr)/2;
        long long k=ans(m);
        if (k==p)
        {
            dr=m;
        }
        else if (k>p)
            dr=m-1;
        else
            st=m+1;
    }
    g<<st<<'\n';
}