#include <bits/stdc++.h>
using namespace std;

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

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

void backtrack(int pos,int luat,long long &ans,long long prod,long long s,long long A){
    if(luat == 1){
        prod *= fact[pos];
        long long add = A/prod;
        s++;
        if(s%2 == 1)
            ans += add;
        else
            ans -= add;
    }
    if(pos+1 < fact.size()){
        backtrack(pos+1,0,ans,prod,s,A);
        backtrack(pos+1,1,ans,prod,s,A);
    }
}

int main(){
    fin>>n>>p;

    long long faken = n;
    for(long long i = 2;i*i<=faken;i++){
        if(faken % i == 0)
            fact.push_back(i);
        while(faken%i == 0)
            faken /= i;
    }

    if(faken > 1)
        fact.push_back(faken);

    long long l=1,r=1,mid,best;

    for(int i=1;i<=61;i++)
        r *= 2;

    if(n==1){
        fout<<p;
        return 0;
    }

    while(l<=r){
        mid = (l+r)/2;
        long long ans = 0;
        backtrack(-1,0,ans,1,0,mid);
        ans = mid - ans;

        if(ans >= p){
            best = mid;
            r = mid - 1;
        }else
            l = mid + 1;
    }
    fout<<best;
}