#include <cstdio>
#include <cmath>

using namespace std;

long long x,b;
int d[100000];
int nrd=0;

bool verif(long long a)
{
    long long rez=0;
    long long pt=1<<nrd;
    for(long long i=1;i<=pt-1;++i)
    {
        long long miau=1;
        long long ham=0;
        for(long long j=0;j<nrd;++j)
        {
            long long m=1<<j;
            if(m&i)
            {
                miau*=d[j+1];
                ham++;
            }
        }
        long long semn;
        if(ham%2==1)
            semn=1;
        else
            semn=-1;
        rez+=semn*(a/miau);
    }
    if(rez<x)
        return 1;
    return 0;
}

int main()
{
    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);
    scanf("%lld %lld",&b,&x);

    for(long long i=2;i<=sqrt(b);++i)
        {
            if(b%i==0)
                {
                    d[++nrd]=i;
                    while(b%i==0)
                        b/=i;
                }
        }
        if(b!=1)
        {
            nrd++;
            d[nrd]=b;
        }
    long long pas=1LL<<61,rez=0;
    while(pas>0)
    {
        if(verif(rez+pas))
            rez+=pas;
        pas/=2;
    }
    printf("%lld",rez+1);
    return 0;
}