#include <fstream>
#include <cstring>
#define DIM 10000005
using namespace std;
ifstream fin("frac.in");
ofstream fout("frac.out");
long long n,i,a,b,s[DIM],P[DIM],solv,x,j,A,p,u,mid,t,unu,k,sol,aa,bb,r;
bool v[DIM],f[DIM];
int main(){
    fin>>a>>b;
    for(i=2;i<=DIM;i++){
        if(v[i]==0){
            s[++x]=i;
            for(j=2;j*i<=DIM;j++){
                v[i]=1;
            }
        }
    }

    A=a;
    for(i=1;i<=x && s[i]<A;i++){
        if(A%s[i]==0){
            P[++n]=s[i];
            while(A%s[i]==0){
                A/=s[i];
            }
        }

    }
    if(A>1){
        P[++n]=A;
    }
    p=1;
    u=(1ll<<62);
    while(p<=u){
        mid=(p+u)>>1;
        solv=mid;
        while(f[0]==0){
            t=n;
            while(f[t]==1){
                f[t]=0;
                t--;
            }
            f[t]=1;
            unu=0;k=1;
            for(i=1;i<=n;i++){
                if(f[i]==1){
                    unu++;
                    k*=P[i];
                }
            }
            if(unu%2==0){
                sol+=solv/k;
            }
            else{
                sol-=solv/k;
            }
        }
        memset(f,0,sizeof(f));
        if(sol>b){
            p=mid+1;
        }
        if(sol<b){
            u=mid-1;
        }
        if(sol==b){
            aa=a;
            bb=mid;
            while(bb!=0){
                r=aa%bb;
                aa=bb;
                bb=r;
            }
            if(aa==1){
                fout<<mid<<"\n";
                return 0;
            }
        }
    }


    return 0;
}