#include <iostream>
#include <fstream>
using namespace std;

#define ll long long

ll N, P, K, V[10010], Ans;

bool DoPinex(ll PossibleSol)
{
    ll CurrentAns = 0;
    for(ll Conf = 0; Conf < (1 << K); Conf ++)
    {
        ll CurrentSign = 0, CurrentProd = 1;
        for(ll i = 0; i < K; i++)
            if(Conf & (1 << i))
            {
                CurrentSign ++;
                CurrentProd *= V[i];
            }
        if(CurrentSign % 2 == 0) CurrentSign = 1;
        else CurrentSign = -1;
        CurrentAns += CurrentSign * PossibleSol / CurrentProd;
    }
    return (CurrentAns >= P);
}

int main()
{
    ifstream cin("frac.in");
    ofstream cout("frac.out");
    cin >> N >> P;
    for(ll i = 2; i * i <= N; i++)
        if(N % i == 0)
        {
            V[K ++] = i;
            while(N % i == 0) N /= i;
        }
    if(N > 1) V[K ++] = N;
    ll Left = 1, Right = (1LL << 62), Mid;
    while(Left <= Right)
    {
        Mid = (Left + Right) / 2;
        if(DoPinex(Mid)) Ans = Mid, Right = Mid - 1;
        else Left = Mid + 1;
    }
    cout << Ans;
    return 0;
}