#include <stdio.h>
int d[50],nrd;
long long cate(long long a, long long b){
    long long i,j,nr,s=0,val;
    for(i=0;i<(1<<nrd);i++){
        val=1;
        nr=0;
        for(j=0;j<nrd;j++)
            if(i&(1<<j)){
                val=val*(long long)d[j];
                nr++;
            }
        if(nr%2==0)
            s+=a/val;
        else
            s-=a/val;
    }
    return s;
}
void divizori(long long b){
    long long i,c=b;
    for(i=2;i*i<=b;i++)
        if(b%i==0){
            d[nrd]=i;
            nrd++;
            while(c%i==0)
                c=c/i;
        }
    if(c!=1){
        d[nrd]=c;
        nrd++;
    }
}
bool prim(long long a,long long b){
    long long r;
    while(b!=0){
        r=a%b;
        a=b;
        b=r;
    }
    if(a==1)
        return true;
    return false;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("frac.in","r");
    fout=fopen("frac.out","w");
    long long b,i,pas,n,nr,rasp=0;
    fscanf(fin,"%lld%lld",&b,&n);
    divizori(b);
    i=0;
    pas=1LL<<61;
    while(pas!=0){
        nr=cate(i+pas,b);
        if(nr<n)
            i+=pas;
        pas/=2;
    }
    rasp=i+1;
    while(prim(rasp,b)==false)
        rasp++;
    fprintf(fout,"%lld",rasp);
    fclose(fin);
    fclose(fout);
    return 0;
}