#include <stdio.h>
#define fr(i,a,b) for(i=a;i<b;++i)
typedef long long ll;
ll s[1024],S,m;
void gen(int i,ll x,int o){
    if(i==m) {if(o>1)s[S++]=x;}
    else gen(i+1,x,o),gen(i+1,-x*s[i],o+1);
    }
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int main(){
    freopen("frac.in","r",stdin);
    freopen("frac.out","w",stdout);
    ll N,n,p,i=2;
    scanf("%lli%lli",&n,&p);
    N=n;
    while(n>1){
        if(!(n%i)){
            while(!(n%i))n/=i;
            s[S++]=i;
            }
        ++i;
        if(S==0 && i*i>n) break;
        }
    if(!S)s[S++]=n;
    m=S;
    gen(0,(ll)-1,0);
    ll l=1,c,r=(ll)1<<61,C;
    --r;
    while(l<r){
        c=(l+r)/2;
        C=c;
        fr(i,0,S)C-=c/s[i];
        if(C==p)break;
        if(C<p) l=c+1;
        else r=c-1;
        }
    while(gcd(c,N)>(ll)1)--c;
    printf("%lli",c);
    return 0;
    }