# include <cstdio>

typedef long long ll ;
const char FIN[] = "frac.in", FOU[] = "frac.out" ;

ll N, P, sol, cnt ;
int fact[20] ;

void desc ( ll N ) {
    for ( int i = 2; 1LL * i * i <= N; ++i ) {
        if ( N % i == 0 ) {
            for ( fact[ ++fact[0] ] = i ; N % i == 0 ; N /= i ) ;
        }
    }

    if ( N > 1 ) {
        fact[ ++fact[0] ] = N ;
    }
}

ll check ( ll X ) {
    ll sol = 0 ;

    for ( int i = 0, aux = 1 << fact[0] ; i < aux ; ++i ) {
        ll nr_mul = 0, elem = 1 ;
        for ( int j = 0; j < fact[0]; ++j ) {
            if ( i & 1 << j ) {
                elem *= ( ll ) fact[j + 1], ++nr_mul ;
            }
        }

        if ( nr_mul & 1 ) {
            nr_mul = - 1 ;
        } else {
            nr_mul = 1 ;
        }

        sol += ( ll ) nr_mul * X / elem ;
    }

    return sol ;
}

int main ( void ) {
    fscanf ( fopen ( FIN, "r" ) , "%lld %lld", &N, &P ) ;
    desc ( N ) ;

    for (sol = 0, cnt = 1LL << 61; cnt; cnt >>= 1) {
        if (check ( sol + cnt ) < P) {
           sol += cnt;
        }
    }

    fprintf ( fopen ( FOU, "w" ) , "%lld", ++sol ) ;

    return 0;
}