#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

vector<long long>v;
long long n,p;

long long cmmdc(long long a,long long b)
{
    int r;
    while(b)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

void putInVector(long long x)
{
    v.clear();
    long long d = 2 , e;
    long long lim = (long long)sqrt((double)n);
    while(d <= lim && x >= 1)
    {
        e = 0;
        while(x % d == 0)
        {
            x /= d;
            e++;
        }
        if(e > 0)
            v.push_back(d);
        d++;
    }
    if(x > 1)
        v.push_back(x);
}

long long gaseste(long long x)
{
    long long st = x ,dr = x;
    long long lim = 1<<61;
    while(st >= 1 || dr <= lim)
    {
        if(cmmdc(st,n) == 1)
            return st;
        if(cmmdc(dr,n) == 1)
            return dr;
        st--;
        dr++;
    }
    return -1;
}

int verif(long long val)
{
    long long sum = 0;
    int ns = (1 << v.size());
    for(int f = 0 ; f < ns ; f++)
    {
        long long rez = 1;
        int ct = 0;
        for(int i = 0 ; i < v.size() ; i++)
        {
            if(f & (1 << i))
            {
                ct++;
                rez *= v[i];
            }
        }
        if(ct == 0)
            continue;
        if(ct & 1)
            sum += (val/rez);
        else
            sum -= (val/rez);
    }
    long long rs = val-sum;
    if(rs > p)
        return 1;
    else if(rs < p)
        return -1;
    else
        return 0;
}

int main()
{
    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);
    scanf("%I64d%I64d",&n,&p);
    long long st,dr,med;
    st = 1;
    dr = 1;
    for(int i = 1 ; i <= 60 ; i++)
        dr <<= 1;
    putInVector(n);
    long long ans=-1;
    while(st <= dr)
    {
        med = (st+dr)/2;
        med = gaseste(med);
        int ch = verif(med);
        if(ch == 0)
        {
            ans = med;
            dr = med-1;
        }
        if(ch == 1)
            dr = med-1;
        else
            st = med+1;

    }
    printf("%lld",ans);
    return 0;
}