#include <iostream>
#include <fstream>
#define nrd 1100000
using namespace std;

ifstream fin ("frac.in");
ofstream fout ("frac.out");

long long nrfac;
long long sol[2000];

long long rez(long long x)
{
    long long z=x, nr, prod, i, j;
    for(i=1; i<(1<<nrfac); i++)
    {
        nr=0; prod=1;
        for(j=0; j<nrfac; j++)
        {
            if((i&(1<<j))!=0)
            {
                nr++;
                prod=prod*sol[j+1];
            }
        }

        if(nr%2==1) z=z-x/prod;
        else z=z+x/prod;
    }
    return z;
}

int main()
{
    long long n, p, i, ct, st, dr, mij, salvez;
    fin>>n>>p;
    //aflu cati factori primi are n
    ct=2;
    while(ct*ct<=n && n>1)
    {
        if(n%ct==0)
        {
            sol[++nrfac]=ct;
            while(n%ct==0) n=n/ct;
        }
        ct++;
    }
    if(n>1) sol[++nrfac]=n;

    //cautarea binara
    st=1;
    dr=(1LL<<61); //2^61
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(rez(mij)<p) st=mij+1;
        else dr=mij-1;
    }
    fout<<st;
}