#include <fstream>
#include <bitset>

#define NMAX 200000

using namespace std;

ifstream f("frac.in") ;
ofstream g("frac.out") ;

long long n , p , nr , n1 , v[50000] , k ;
bitset <NMAX> c ;

void ciur(){

    c[1] = c[0] = 1 ;
    for(long long i = 2 ; i * i < NMAX ; ++i){
        if(c[i] == 0){
            for(long long j = i * i ; j < NMAX ; j += i){
                c[j] = 1 ;
            }
        }
    }
}

long long solve(long long n1){
    nr = n1 ;

    for(long long i = 1 ; i < (1 << k) ; ++i){
        long long x = 0 , prod = 1 ;

        for(long long j = 0 ; j < k ; ++j){
            if(i & (1 << j)){
                prod = prod * v[j + 1] ;
                ++x;
            }
        }
        if(x % 2){
            nr -= n1 / prod ;
        }
        else{
            nr += n1 / prod ;
        }
    }

    return nr ;
}

long long caut_bin(long long n , long long val){
    long long p = 0 , i ;

    for(i = 1 ; i <= n ; i <<= 1);
    while(i){
        if(solve(i + p) < val){
            p += i ;
        }
        i >>= 1 ;
    }
    return p + 1 ;
}

int main()
{
    ciur();

    f >> n >> p ;

    n1 = n ;
    nr = n ;

    int x = 2 ;

    while(n != 1 && x * x <= n){
        if(n % x == 0){
            v[++k] = x ;
            while(n % x == 0){
                n /= x ;
            }
        }
        ++x ;
    }

    if(n != 1){
        v[++k] = n ;
    }

    nr = solve(n1) ;

    if(p % nr == 0){
        g << n1 * (p / nr - 1) + caut_bin(n1 , nr) ;
        return 0 ;
    }

    g << n1 * (p / nr) + caut_bin(n1 , p % nr) ;

    return 0;
}