///Alexandru Morus
#include <bits/stdc++.h>

using namespace std;
ifstream in("frac.in");
ofstream out ("frac.out");
long long v[1000009],p[1000009],num,aok[1000009];
void ciur()
{
    long long i,j,cnt = 0;
    v[1] = 1;
    v[0] = 1;
    for(i = 2; i <= 400005; i ++)
    {
        if(!v[i])
        {
            p[num] = i;
            num ++;
            for(j = i * 2;j <= 400005; j += i)
            {
                v[j] = 1;
            }
        }
    }
}
long long c2(long long n, long long a)
{
    long long cnt = 0,i,af = 0,j;
    for(i = 0; i <= num; i ++)
    {
        if(n % p[i] == 0)
        {
            aok[cnt] = p[i];
            cnt ++;
        }
        while(n % p[i] == 0)
        {
            n = n / p[i];
        }
        if(n == 1)
        {
            break;
        }
    }
    if(n > 1)
    {
        aok[cnt] = n;
        cnt ++;
    }
    cnt --;
    for(i = 0; i < 1 << (cnt + 1); i ++)
    {
        long long aa = 1;
        long long nr_b = 0;
        for(j = 0; j <= cnt; j ++)
        {
            if((i >> j) & 1)
            {
                aa = aa * aok[j];
                nr_b ++;
            }
        }
        if(nr_b % 2 == 0)
        {
            af += a / aa;
        }
        else
        {
            af -= a / aa;
        }
    }
    return af;
}
int main()
{
    long long m,q,a,b,i,j,nr,st = 1;
    long long dr = ((long long) 1 << 61);
    long long af = ((long long) 1 << 61);
    ciur();
    in >> b >> nr;
    while(st <= dr)
    {
        long long mid = (st + dr) / 2;
        long long r = c2(b,mid);
        if(r == nr)
        {
            if(mid < af)
            {
                af = mid;
                dr = mid - 1;
            }
        }
        else if(r < nr)
        {
            st = mid + 1;
        }
        else
        {
            dr = mid - 1;
        }
    }
    out << af;
    return 0;
}