#include <bits/stdc++.h>

using namespace std;

ifstream f("frac.in");
ofstream g("frac.out");

long long m,sol[1101];

long long pinex(long long A)
{
    long long nr,i,prod,j,S=0;
    for(i=1;i<(1<<m);i++)
    {
        nr=0;
        prod=1;
        for(j=0;j<m;j++)
            if((i&(1<<j))!=0)
            {
                nr++;
                prod=prod*sol[j+1];
            }

        if(nr%2==1)S=S+A/prod;
        else S=S-A/prod;
    }

    return A-S;
}

long long a,SOL,t,i,j,p,u,nr,mij,prim[1000010],d,b;
bool ciur[1000010];

int main()
{
    f>>a>>b;
    swap(a,b);

    for(d=2;d<=1000001;d++)
    if(ciur[d]==0)
    {
        t++,prim[t]=d;
        for(i=d*d;i<=1000001;i=i+d)ciur[i]=1;
    }

    j=1;
    while(prim[j]*prim[j]<=b)
    {
        if(b%prim[j]==0)
        {
            while(b%prim[j]==0)b=b/prim[j];
            m++;
            sol[m]=prim[j];
        }
        j++;
    }

    if(b!=1)
    {
        m++;
        sol[m]=b;
    }


    p=1;
    u=100000000000000;

    while(p<=u)
    {
        mij=(p+u)/2;
        nr=pinex(mij);

        if(nr>=a){SOL=mij;u=mij-1;}
        else {p=mij+1;}

    }
    g<<SOL;
    return 0;
}