#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ( "frac.in" );
ofstream fout ( "frac.out" );

long long v[65];

int main ( ) {
    
    long long st, dr, mij, n, p, i, a, d, x;
    
    fin >> n >> p;
    
    x = 0;
    
    for ( d = 2; d * d <= n; d++ ){
        
        if ( n % d == 0 ) {
            v[x] = d;
            x++;
        }
        
        while ( n % d == 0 )
            n = n / d;
    }
    
    if ( n > 1 )
        v[x++] = n;
    
    st = 1;
    dr = 1e18;
    
    while ( dr - st > 1 ) {
        
        mij = ( st + dr ) / 2;
        
        a = 0;
        
        for ( int mask = 0; mask < ( 1 << x ); mask++ ) {
            
            long long s = 1, prod = 1;
            
            for( i = 0; i < x; i++ ) {
                if ( ( mask >> i ) & 1 ) {
                    s = -s;
                    prod = prod * v[i];
                }
            }
            
            a = a + mij / prod * s;
        }
        
        if ( a >= p )
            dr = mij;
        else
            st = mij;
    }
    
    fout << st + 1;
    
    return 0;
}