#include <fstream>
#include <iostream>
#include <bitset>
#define MAXN DIM
#define DIM 120002
using namespace std;

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

bitset <MAXN> v;
bitset <70> s;
long long prim[DIM],a[DIM],k,p,u,sol_max,N,P,x;
void ciur(){
    v[0]=v[1]=1;
    for(int i=2;i<=MAXN;i++)
    if(!v[i]){
        prim[++k]=i;
        for(int j=i+i;j<=MAXN;j+=i)
            v[j]=1;
    }
}
void haha(int B){
    for(long long i=1;i<=k && prim[i]*prim[i]<=B;i++)
        if(B%prim[i]==0){
            a[++x]=prim[i];
            while(B%prim[i]==0)
                B/=prim[i];
        }
    if(B>1)
        a[++x]=B;
}
long long solve(long long A){
    s.reset();
    s[x]=1;
    long long sol=0;
    while(!s[0]){
        long long par,p;
        par=0;
        p=1;
        for(int i=1;i<=x;i++)
            if(s[i]){
                par++;
                p*=a[i];
            }
        if(par%2)
            sol+=A/p;
        else
            sol-=A/p;
        int j=x;
        while(s[j]){
            s[j]=0;
            j--;
        }
        s[j]=1;
    }
    return A-sol;
}
long long cmmdc(long long a,long long b){
    long long r;
    while(b!=0){
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main(){
    ciur();
    fin>>N>>P;
    p=1;
    u=(1ll<<62);
    haha(N);
    while(p<=u){
        long long mid=(p+u)>>1;
        long long sol=solve(mid);
        if(sol<P)
            p=mid+1;
        if(sol>P)
            u=mid-1;
        if(sol==P){
            if(cmmdc(N,mid)==1){
                sol_max=mid;
                p=u+1;
            }
            else
                u=mid-1;
        }
    }
    fout<<sol_max;
    fin.close();fout.close();
    return 0;
}