#include<stdio.h>
#include<math.h>
using namespace std;

FILE*f=fopen("frac.in","r");
FILE*g=fopen("frac.out","w");

long long div[5000],cn,x,n,p,i,j,ok,dim,nrp,nr,p1,p2;

int prim(long long x) {
    int r;
    r=x%cn;
    while(r) {
    x=cn;
    cn=r;
    r=x%cn;
    }
    if(cn==1) return 1;
    else return 0;
}

int main() {

    fscanf(f,"%lld%lld",&n,&p);

    p2=1; p1=1; cn=n;
    for(i=2;i<=sqrt(n)&&n!=1;i++) {
        ok=0;
        while(n%i==0) {n=n/i; ok=1;}
        if(ok==1) { p1=p1*i; p2=p2*(i-1);}
    }
    if(n!=1) { p1=p1*n; p2=p2*(n-1);}

    n=cn;

    if(n*p2/p1<p) {
        x=(p-1)*p1/p2;
        while(x%p1!=0) x--;
        while(prim(x)==0) {x++; cn=n;}
        fprintf(g,"%lld",x);
    }
    else {
        nrp=n*p2/p1; x=n;
        while(nrp>p) {
            cn=n;
            if(prim(x)==1) nrp--;
            x--;
        }
        fprintf(g,"%lld",x+1);
    }


    return 0;
}