#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
long long v[110005], nr;
long long n, p, st, dr, mid;
short f[110005];
void pinex( long long &ans ){
    memset( f, 0, sizeof(f) );
    while( f[0] != 1 ){
        long long i = nr;
        while( f[i] == 1 ){
            f[i] = 0;
            i--;
        }
        f[i] = 1;
        if( i == 0 ){
            break;
        }
        long long nr1 = 0;
        long long prod = 1;
        for( long long j = 1; j <= nr; j++ ){
            if( f[j] == 1 ){
                nr1++;
                prod *= 1LL * v[j];
            }
        }
        long long semn = 1;
        if( nr1 % 2 == 0 ){
            semn = -1;
        }
        ans += ( mid / prod ) * semn;
    }
    return ;
}
int good(){
    long long ans = 0;
    pinex( ans );
    if( mid - ans >= p ){
        return 1;
    }
    return 0;
}
int main(){
    fin >> n >> p;
    long long save = n;
    for( long long i = 2; i * i <= save; i++ ){
        if( n % i == 0 ){
            v[++nr] = i;
            while( n % i == 0 ){
                n /= i;
            }
        }
    }
    if( n > 1 ){
        v[++nr] = n;
    }
    n = save;
    st = 1LL;
    dr = (1LL<<61);
    long long r = 0;
    while( st <= dr ){
        mid = ( st + dr ) / 2;
        if( good() == 1 ){
            dr = mid - 1;
        }else{
            st = mid + 1;
            r = mid;
        }
    }
    fout << r + 1;
    return 0;
}